ฉันต้องคำนวณความซับซ้อนของเวลาทำงานของฟังก์ชันในแง่ของ n (สำหรับตัวอย่าง O(n)) n คือ len(lst) , lst เป็นตัวแปรประเภทรายการ
นี่คือสิ่งที่ฉันคิดใช่ไหม? (ฉันต้องหาขอบเขตที่แน่นที่สุด!!!) 
คำนวณความซับซ้อนของฟังก์ชัน hw ใน python
คำตอบ (1)
โอเค มันเป็นปัญหาที่ค่อนข้างซับซ้อน และค่อนข้างสนุกสำหรับการทำการบ้าน
ประการแรก เห็นได้ชัดว่าคุณต้องแบ่งปัญหาออกเป็นสองส่วน ไม่ว่า n จะมากกว่า 100,000 หรือไม่ก็ตาม
ถ้า n มากกว่า 100,000:
คุณจะรันวงในสุดสูงสุด 20,000 ครั้งในคราวเดียว (เพราะเมื่อ j มีขนาดใหญ่กว่า 100,000 k loop ของคุณจะส่งผลให้เกิดการวนซ้ำ 0 ครั้ง) ดังนั้นสำหรับทุกการจำลอง สำหรับส่วนของ n ที่สูงกว่า 50,000 คุณจะต้องดำเนินการอย่างแน่นอน
ลูปทั้งหมด มันให้
. คุณต้องบวกเวลาในการคำนวณส่วน i ‹ 50 000 (n ‹ 100 000) ซึ่งสามารถเขียนเป็น
,
ที่ให้ 
หมายความว่าค่าที่สูงกว่า n = 100,000 ปัญหาของคุณมีความซับซ้อน O(n) ที่ชัดเจน โดยที่ส่วนที่คงที่มีขนาดเล็กกว่าเส้นตรงตั้งแต่หนึ่งขนาดขึ้นไป:
ส่วนที่ยุ่งยากมาถึงเมื่อคุณมีค่าต่ำกว่า n = 100,000 คุณสามารถเขียนได้ที่นี่
,
ซึ่งสามารถแปลงร่างเป็น:
ฟังก์ชันนี้แสดงการเพิ่มขึ้นเชิงเส้นพร้อมการลดลงแบบยกกำลังสอง เดาว่ารากของมันอยู่ที่ไหน… (เกือบ) เป๊ะๆ ที่ 100,000
การคำนวณผลรวมและปล่อยให้ O(1), O(n) และส่วนที่ไม่มีนัยสำคัญที่คุณได้รับ:
คุณจะเห็นว่าส่วนของลูกบาศก์นั้นเป็นลบ ดังนั้นเวลาจะต่ำกว่า 0 สำหรับ n-s ขนาดใหญ่ แต่คุณจะเห็นได้ว่าที่ n = 100,000 ส่วนกำลังสองยังคงมีขนาดใหญ่กว่าลูกบาศก์ 1 ถึง 3 เท่า และค่าสูงสุดของฟังก์ชันอยู่ที่ n = 200,000 ดังนั้นอย่ากังวล คุณจะไม่เข้าไปในนั้น คูณด้วยค่าลบ ที่จริงแล้ว คุณจะไปไม่ถึงค่าสูงสุดของฟังก์ชันนี้ด้วยซ้ำ
คุณจะตีความสิ่งนี้ได้อย่างไร? ในกรณีที่แย่ที่สุด คุณมีความซับซ้อน O(n2) แต่คุณมีลำดับที่ลดลงสูงกว่า และสำหรับ n-s ขนาดใหญ่ที่ต่ำกว่า 100,000 คุณสามารถทำอะไรได้ดีกว่า O(n2) ที่คาดการณ์ไว้มาก (สูงสุด 33%)
สรุป:
- ถ้า n น้อยกว่า 100,000 มาก: O(n2)
- ถ้า n ปิด แต่น้อยกว่า 100,000: ค่อนข้างดีกว่า O(n2)
- ถ้า n มากกว่า 100,000: O(n)
ฉันเรียกใช้ตัวอย่างเพื่อวัดสิ่งที่เกิดขึ้น ฉันใช้ตัวเลขที่แตกต่างกัน (เพราะปัญหาเดิมของคุณจะคงอยู่ตลอดไป) ดังนั้นค่าเกณฑ์ 100,000 ของคุณจึงอยู่ที่ 100 ในกรณีของฉัน คุณจะเห็นว่าในตอนแรก O(n2) ทำงานได้ดี จากนั้น O(n2-n3) ก็เข้ากับความซับซ้อนได้ดี ในที่สุด เมื่อเกิน 100 เราก็เข้าสู่ส่วนเชิงเส้น
และสำหรับ n-s ขนาดใหญ่ (ยังคงมีเกณฑ์อยู่ที่ 100):
person
leeladam
schedule
07.12.2013
ฉันไม่เชื่อว่าสิ่งนี้ถูกต้อง เหนือขีดจำกัด การวนซ้ำ
k จะเสร็จสมบูรณ์ในเวลาคงที่ ในขณะที่การวนซ้ำ i และ j อยู่ในลำดับ n สำหรับค่า n ที่มีขนาดใหญ่ ฟังก์ชันโดยรวมคือ O(n^2) ลูปทั้งหมดอยู่ต่ำกว่าเกณฑ์ n ทำให้ฟังก์ชัน O(n^3) ฉันตั้งเวลาฟังก์ชันสำหรับค่า n ขนาดใหญ่โดยมีเกณฑ์เป็น 100 และเห็นได้ชัดว่าไม่เป็นเชิงเส้น i.imgur.com/i1Fglwc.png
- person Tim; 08.12.2013
@Tim: มันไม่ใช่แค่ k เท่านั้น แต่ j loop ที่เสร็จสิ้นในเวลาคงที่สำหรับ n › 10^5 ! เพราะเฉพาะส่วน j ในช่วง (10^5) เท่านั้นที่จะให้อะไรก็ได้ (ซึ่งเป็นค่าคงที่) และ j ในช่วง (10^5,n) จะไม่ทำอะไรเลย! ฉันไม่สามารถสร้างผลลัพธ์ของคุณได้ ฉันได้รับการพึ่งพาเชิงเส้นมากถึง 10,000 โดยมีเกณฑ์อยู่ที่ 100 (ดูคำตอบที่แก้ไข) ในทางกลับกัน โปรดทราบว่าส่วน n^3 ของคุณกำลังลดระดับลง เนื่องจากในลูปด้านใน j-s ขนาดใหญ่จะทำงานเร็ว และ j-s ขนาดเล็กจะทำงานช้า! คุณมีการพึ่งพา O(n3) แต่มันเป็นลบ และส่วนนำคือ O(n2) เท่านั้น
- person leeladam; 08.12.2013
for j in range(i) จะปรับขนาดเป็นเส้นตรง - ไม่เสร็จสมบูรณ์ในเวลาคงที่ ดูเหมือนว่าคุณกำลังใช้รหัสอื่นกับผู้ถาม
- person Tim; 08.12.2013
@Tim: ฉันยังไม่เห็นด้วย แต่มันเป็นไปได้อย่างแน่นอนว่าคุณพูดถูก คุณควรเขียนวิธีแก้ปัญหาของคุณเป็นคำตอบสำหรับ OP และฉันจะพยายามอย่างเต็มที่เพื่อทำความเข้าใจ
- person leeladam; 08.12.2013
k) คงที่ ค่าทั้งหมดควรเป็น O(n^2) ฉันไม่แน่ใจว่ามันจะคงที่หรือเปล่าเมื่อมันเชิงเส้นถึงจุดหนึ่งแล้วคงที่... - person Tim schedule 07.12.2013