Proof. Choose a row having a minimu

Proof. Choose a row having a minimum number of ones. Construct the matrix
M c as in the previous lemma. Each row will have no more than the number of ones
it originally contained plus the number of ones produced by complementation.
This at most doubles the total number of ones in the matrix.
M c can be constructed by scanning a list of the nonzero entries of M. The complementation
is easily performed using list handling techniques. Since each one
is only processed a fixed number of times, independent of the size of M, the total
time required is O(m + n + f).

ผลลัพธ์ (ไทย) 1:

หลักฐาน เลือกแถวที่มีจำนวนขั้นต่ำคน สร้างเมตริกซ์M c เช่นหน่วยการก่อนหน้านี้ แต่ละแถวจะมีจำนวนคนไม่เกินมันมีอยู่เดิม บวกกับจำนวนที่ผลิต โดยเสริมฤทธิ์ complementationนี้มากที่สุดคู่จำนวนรวมของคนในเมตริกซ์M c สามารถสร้างได้ โดยการสแกนรายการของรายการค่าของ M การเสริมฤทธิ์ complementationทำรายการการจัดการเทคนิคใช้ง่าย ตั้งแต่ละคนมีเพียงจำนวนคงที่ของเวลา อิสระของขนาดของ M รวมการประมวลผลใช้เวลาเป็น O (m + n + f)

ผลลัพธ์ (ไทย) 2:

พิสูจน์ เลือกแถวมีจำนวนขั้นต่ำของคน สร้างเมทริกซ์
M C ในขณะที่แทรกก่อนหน้านี้ แต่ละแถวจะต้องไม่เกินกว่าจำนวนของคนที่
มันมีมา แต่เดิมบวกกับจำนวนของคนที่ผลิตโดย complementation ได้.
นี้ที่มากที่สุดคู่จำนวนรวมของคนในเมทริกซ์.
เอ็มซีสามารถถูกสร้างขึ้นโดยการสแกนรายชื่อของรายการภัณฑ์ของ เอ็ม complementation
จะดำเนินการได้อย่างง่ายดายโดยใช้เทคนิคการจัดการรายการ เนื่องจากแต่ละคน
มีการประมวลผลเพียงจำนวนคงที่ของเวลาเป็นอิสระจากขนาดของ M, รวม
ระยะเวลาที่ต้องเป็น O (m + n + F)

ผลลัพธ์ (ไทย) 3:

พิสูจน์ เลือกแถวมีจำนวนขั้นต่ำของคน การสร้างเมทริกซ์M C ในรูปแบบเดิม แต่ละแถวจะมีมากกว่าจำนวนคนปกติมันมีบวกจำนวนที่ผลิตโดยเอนไซม์ .นี้ที่ส่วนใหญ่เป็นสองเท่าของจำนวนคนที่อยู่ในเมทริกซ์M C สามารถสร้างขึ้นโดยการสแกนรายชื่อของรายการที่ศูนย์ของ M Complementationได้อย่างง่ายดายโดยใช้รายการการจัดการเทคนิค เพราะแต่ละคนเป็นเพียงการประมวลผลการกำหนดจำนวนครั้ง ขึ้นอยู่ขนาดของ M , รวมต้องใช้เวลาเป็น O ( M + N + F )