ฉันมีวงวนง่าย ๆ เช่นนี้:
for (int i = 0; i < n; i++) {
// constant time operation
}
ง่ายมากที่จะเห็นว่ามันมีความซับซ้อนของเวลา O(n) แต่ถ้าเราคำนวณมัน ทำไมมันจึงเป็น 2*n + 2 + c*n (ให้คำตอบมา) ไม่ใช่ (1+ (n+1) + 2*n + c*n) = (3+c)*n + 2? ฉันเห็นว่า i++ เป็นการดำเนินการ 2 อย่าง: การบวกและการมอบหมาย; ดังนั้นจึงควรเป็น 2*n และการดำเนินการคงที่จะดำเนินการ n ครั้ง ดังนั้นจึงเป็น c*n
2*n
(n การเปรียบเทียบ (i<n) + n เพิ่มขึ้น (i++)) == 2*n
2
(i=0 1 สำหรับการมอบหมาย + 1 สำหรับการจัดสรร i) == 2
c*n
(n การดำเนินการตามเวลาคงที่) == c*n
จากสิ่งที่ฉันบอกได้ การเพิ่มขึ้น/ลดลงจะถือเป็นการดำเนินการครั้งเดียว สิ่งนี้สมเหตุสมผลเพราะในแอสเซมบลี คุณสามารถดำเนินการเพิ่มหรือลดได้ด้วยโค้ดแอสเซมบลีบรรทัดเดียว นอกจากนี้ บรรทัดโค้ดแอสเซมบลีส่วนใหญ่แปลโดยตรงเป็นคำสั่งไบนารี่คำสั่งเดียว ดังนั้นการเพิ่ม/ลดจึงเป็นการดำเนินการตามเวลาคงที่อย่างมีประสิทธิภาพ
ดังนั้นเราจึงไม่มีการดำเนินการจากการเพิ่มขึ้น นอกจากนี้ เรายังรันเนื้อความของลูป n ครั้ง และเนื้อความของลูปดำเนินการตามเวลาคงที่ ดังนั้นเราจึงมีการดำเนินการ c * n เพิ่มเติม เมื่อเราเข้าสู่วงในครั้งแรกจะมีการดำเนินการมอบหมายเพิ่มเติม สิ่งนี้ให้ผลการดำเนินการอื่น สุดท้าย หลังจากที่ลูปรันเป็นครั้งที่ n ลูปจะตรวจสอบสภาพของลูปอีกครั้งหนึ่ง ซึ่งหมายความว่ามีการเปรียบเทียบ n + 1 ที่ลูปดำเนินการ
เมื่อบวกเข้าด้วยกัน เราจะได้ n + c * n + 1 + (n + 1) = 2 * n + c * n + 2 ซึ่งเป็นคำตอบที่คุณเห็น
