ฉันได้สูตรนี้จากหนังสือโครงสร้างข้อมูลในอัลกอริธึมการเรียงลำดับแบบฟอง
ฉันรู้ว่าเราเป็น (n-1) * (n ครั้ง) แต่ทำไมต้องหารด้วย 2?
ใครช่วยกรุณาอธิบายเรื่องนี้ให้ฉันฟังหรือให้หลักฐานโดยละเอียด
ขอบคุณ
ข้อพิสูจน์ของ (N–1) + (N–2) + (N–3) + + 1= N*(N–1)/2 [ปิด]
คำตอบ (9)
person
Viral Shah
schedule
20.03.2010
ขอบคุณครับ ผมชอบเทคนิคเหล่านี้ในการอธิบายข้อพิสูจน์ของสูตรนี้ โดยเฉพาะเทคนิคข้อ 3 ดูได้ที่ betterexplained.com/articles/
- person skystar7; 21.03.2010
(N-1) + (N-2) +...+ 2 + 1 คือผลรวมของรายการ N-1 ตอนนี้เรียงลำดับรายการใหม่ โดยที่หลังจากตัวแรกมาถึงตัวสุดท้าย จากนั้นตัวที่สอง และตัวที่สองตามลำดับ เช่น (N-1) + 1 + (N-2) + 2 +.. วิธีการเรียงลำดับสินค้าตอนนี้ คุณจะเห็นว่าแต่ละคู่มีค่าเท่ากับ N (N-1+1 คือ N, N-2+2 คือ N) เนื่องจากมีรายการ N-1 จึงมี (N-1)/2 คู่ดังกล่าว คุณกำลังบวก N (N-1)/2 ครั้ง ดังนั้นค่ารวมคือ N*(N-1)/2
person
sepp2k
schedule
20.03.2010
เริ่มจากสามเหลี่ยม...
*
**
***
****
คิดเป็น 1+2+3+4 จนถึงตอนนี้ ตัดสามเหลี่ยมครึ่งตามมิติเดียว...
*
**
* **
** **
หมุนส่วนที่เล็กกว่า 180 องศา แล้วติดไว้ด้านบนของส่วนที่ใหญ่กว่า...
**
*
*
**
**
**
ปิดช่องว่างเพื่อให้ได้รูปสี่เหลี่ยมผืนผ้า
ตั้งแต่แรกเห็น วิธีนี้ใช้ได้ก็ต่อเมื่อฐานของสี่เหลี่ยมผืนผ้ามีความยาวเท่ากัน แต่ถ้ามีความยาวเป็นเลขคี่ คุณก็แค่ตัดคอลัมน์ตรงกลางออกครึ่งหนึ่ง ซึ่งยังคงใช้ได้กับความกว้างครึ่งหน่วยสองเท่าของความสูง ( พื้นที่จำนวนเต็มยังคงเป็น) แถบด้านหนึ่งของสี่เหลี่ยมของคุณ
ไม่ว่าฐานของสามเหลี่ยมจะเป็นเท่าใด ความกว้างของสี่เหลี่ยมผืนผ้าของคุณคือ (base / 2) และความสูงคือ (base + 1) ซึ่งให้ ((base + 1) * base) / 2
อย่างไรก็ตาม base ของฉันคือ n-1 ของคุณ เนื่องจากการเรียงลำดับแบบบับเบิลจะเปรียบเทียบคู่ของรายการในแต่ละครั้ง ดังนั้นจึงวนซ้ำเฉพาะตำแหน่ง (n-1) สำหรับลูปแรก
person
Steve314
schedule
20.03.2010
ลองสร้างคู่ตัวเลขจากเซต อันแรก + อันสุดท้าย; อันที่สอง + อันก่อนหน้าอันสุดท้าย มันหมายถึง n-1 + 1; n-2 + 2 ผลลัพธ์จะเป็น n เสมอ และเนื่องจากคุณบวกตัวเลขสองตัวเข้าด้วยกัน จึงมีเพียง (n-1)/2 คู่เท่านั้นที่สามารถสร้างจากตัวเลข (n-1) ได้
มันก็เหมือนกับ (N-1)/2 * N
person
gius
schedule
20.03.2010
ฉันรู้ว่าเราเป็น (n-1) * (n ครั้ง) แต่ทำไมต้องหารด้วย 2?
จะเป็น (n - 1) * n เท่านั้น หากคุณใช้ฟองสบู่แบบไร้เดียงสา คุณสามารถประหยัดเงินได้มากหากคุณสังเกตเห็นสิ่งต่อไปนี้:
หลังจากการเปรียบเทียบและสลับแต่ละครั้ง องค์ประกอบที่ใหญ่ที่สุดที่คุณพบจะอยู่ในจุดสุดท้ายที่คุณอยู่
หลังจากผ่านครั้งแรก องค์ประกอบที่ใหญ่ที่สุดจะอยู่ในตำแหน่งสุดท้าย หลังจากที่ผ่าน kth องค์ประกอบที่ใหญ่ที่สุด kth จะอยู่ในตำแหน่งสุดท้ายที่ kth
ดังนั้นคุณไม่จำเป็นต้องเรียงลำดับทั้งหมดทุกครั้ง: คุณเพียงแค่ต้องเรียงลำดับองค์ประกอบ n - 2 รายการในครั้งที่สอง, n - 3 องค์ประกอบในครั้งที่สาม และต่อๆ ไป นั่นหมายความว่าจำนวนการเปรียบเทียบ/การแลกเปลี่ยนทั้งหมดที่คุณต้องทำคือ (n - 1) + (n - 2) + ... นี่คืออนุกรมเลขคณิต และสมการสำหรับจำนวนรวมของ ครั้ง คือ (n - 1)*n / 2
ตัวอย่าง: หากขนาดของรายการคือ N = 5 คุณจะทำ 4 + 3 + 2 + 1 = 10 สวอป -- และสังเกตว่า 10 เท่ากับ 4 * 5 / 2
person
John Feminella
schedule
20.03.2010
แต่ก็มีเขียนไว้ด้วยว่า n(n - 1)/2 หรือ O(n^2) หรือ n^2 งั้นกำลังสองของ n คือกำลังสองของ 5 เท่ากับ 25 แต่ n(n-1)/2 เท่ากับ 10 เป็นไปได้ยังไง?
- person Harinder; 15.03.2015
@Harinder: หรือ O(n^2) หรือ n^2 .... ไม่ O(n^2) == n^2 ไม่ถูกต้อง
n^2 + 1,000,000 ก็เป็น O(n^2) เช่นกัน แต่เห็นได้ชัดว่าไม่เท่ากับ n^2
- person John Feminella; 15.03.2015
นี่คือสิ่งที่ฉันไม่เข้าใจ ตัวอย่างเช่น ดูที่ sparknotes.com/cs/sorting/bubble/section1.rhtml . นอกจากนี้ยังระบุด้วยว่าท้ายที่สุดแล้วกรณีที่ค่าเฉลี่ยและเลวร้ายที่สุดคือ n^2
- person Harinder; 15.03.2015
และนี่ก็ถูกต้องเช่นกัน n(n - 1)/2 หรือ O(n^2)?? ถ้าเป็นเช่นนั้นมันกลายเป็น O(n^2) ได้อย่างไร
- person Harinder; 15.03.2015
@Harinder: คุณควรถามคำถาม SO แยกต่างหาก ความคิดเห็นไม่ค่อยดีนักสำหรับการตอบเรื่องยาวๆ
- person John Feminella; 15.03.2015
ผลรวมของความก้าวหน้าทางคณิตศาสตร์
(A1+AN)/2*N = (1 + (N-1))/2*(N-1) = N*(N-1)/2
person
ShPavel
schedule
20.03.2010
นี่เป็นข้อพิสูจน์ที่ค่อนข้างธรรมดา วิธีหนึ่งที่จะพิสูจน์สิ่งนี้คือการใช้การอุปนัยทางคณิตศาสตร์ นี่คือลิงค์: http://zimmer.csufresno.edu/~larryc/proofs/proofs.mathinduction.html
person
John Kane
schedule
20.03.2010
สมมติว่า n=2 จากนั้นเราจะได้ 2-1 = 1 ทางด้านซ้าย และ 2*1/2 = 1 ทางด้านขวา
แสดงว่า f(n) = (n-1)+(n-2)+(n-3)+...+1
ตอนนี้สมมติว่าเราได้ทดสอบจนถึง n=k จากนั้นเราจะต้องทดสอบหา n=k+1
ทางด้านซ้ายเรามี k+(k-1)+(k-2)+...+1 ดังนั้นมันคือ f(k)+k
ทางขวาเราจะได้ (k+1)*k/2 = (k^2+k)/2 = (k^2 +2k - k)/2 = k+(k-1)k/ 2 = kฉ(k)
นี่ต้องคงไว้ทุก ๆ k และนี่เป็นการสรุปการพิสูจน์
person
martiert
schedule
20.03.2010
นี่คือข้อพิสูจน์โดยการอุปนัย โดยพิจารณาจากเงื่อนไข N แต่จะเหมือนกันสำหรับ N - 1:
สำหรับ N = 0 สูตรจะเป็นจริงอย่างเห็นได้ชัด
สมมติว่า 1 + 2 + 3 + ... + N = N(N + 1) / 2 เป็นจริงสำหรับ N ตามธรรมชาติบางค่า
เราจะพิสูจน์ว่า 1 + 2 + 3 + ... + N + (N + 1) = (N + 1)(N + 2) / 2 เป็นจริงเช่นกันโดยใช้สมมติฐานก่อนหน้านี้:
1 + 2 + 3 + ... + N + (N + 1) = (N(N + 1) / 2) + (N + 1)
= (N + 1)((N / 2) + 1)
= (N + 1)(N + 2) / 2.
ดังนั้นสูตรนี้จะคงไว้สำหรับ N ทั้งหมด
person
IVlad
schedule
20.03.2010
สมมติว่า P(N) เป็นจริงสำหรับ N ตามธรรมชาติทั้งหมด นั่นไม่ใช่ข้อพิสูจน์ที่ถูกต้องโดยการเหนี่ยวนำ คุณกำลังตั้งเป้าที่จะพิสูจน์ P(N) =› P(N+1) ดังนั้นคุณควรถือว่า P(N) เป็นจริงสำหรับ บางส่วน N หากคุณถือว่ามันเป็น ทั้งหมด< /i> N ถ้าอย่างนั้นคุณก็ถามคำถาม
- person Steve Jessop; 20.03.2010
Nทางด้านซ้าย หากไม่เป็นเช่นนั้น แสดงว่าNหายไปหนึ่งรายการ ดังนั้น2Nจึงควรถูกลบในตัวเศษ - person Johannes Schaub - litb schedule 20.03.2010n- person Ken schedule 20.03.2010Nไม่ได้รวมอยู่ด้วย (โดยปกติแล้วจะเป็นเช่นนั้นพร้อมกับคำชี้แจงปัญหานี้) โด้! - person Stephan202 schedule 20.03.2010