การค้นหาโหนดในความซับซ้อนของเวลารายการที่ลิงก์เดี่ยว

ฉันมีคำถามนี้ในการทดสอบกลางภาคของหลักสูตร DSA:

พิจารณา Single Linked List ที่มี N โหนด (N > 8) วิธี f1() ได้รับการออกแบบมาเพื่อค้นหาโหนดที่ 8 ตั้งแต่เริ่มต้น และวิธี f2() ได้รับการออกแบบมาเพื่อค้นหาโหนดที่ 8 จากจุดสิ้นสุด ความซับซ้อนของเวลาของ f1() และ f2() คือข้อใด

เลือกหนึ่งอัน:

ก. ซ้ำแล้วซ้ำอีก)

ข. โอ(1) และโอ(1)

ค. O(1) และ O(N)

ง. โอ(N) และ โอ(1)

คำตอบที่ถูกต้องคือค. O(1) และ O(N) อย่างไรก็ตาม ฉันคิดว่าคำตอบที่ถูกต้องคือ ก. ฉันรู้ว่าถ้า N = 8 จะต้องใช้เวลา O(1) ในการค้นหาโหนดที่ 8 จากจุดเริ่มต้น (เพียงส่งคืนโหนดส่วนท้าย) แต่ในกรณีนี้ N > 8 ใครช่วยอธิบายสิ่งนี้ให้ฉันหน่อยได้ไหม

ขอขอบคุณล่วงหน้าสำหรับความช่วยเหลือที่คุณสามารถให้ได้


list algorithm data-structures linked-list singly-linked-list
person L.I.B L.I.B    schedule 18.05.2016    source แหล่งที่มา
comment
คำตอบที่ให้มานั้นถูกต้อง คุณไม่ใช่ คุณต้องดำเนินการกี่ครั้งเพื่อส่งคืนโหนดที่ 8 จาก 1,000 จาก 1000000?   -  person n. 1.8e9-where's-my-share m.    schedule 18.05.2016
comment
ค. ถูกต้องที่สุดแต่ก. ก็ถูกต้องทางเทคนิคเช่นกัน เนื่องจากสิ่งใดก็ตามที่เป็น O(1) ก็คือ O(N) เช่นกัน   -  person Paul Hankin    schedule 19.05.2016

คำตอบ (1)


arrow_upward
1
arrow_downward

O(1) หมายถึงเวลาทำงานคงที่ กล่าวอีกนัยหนึ่ง มันไม่ได้ขึ้นอยู่กับขนาดอินพุต

เมื่อคุณใช้คำจำกัดความนั้นที่นี่ คุณจะเห็นว่าการดึงองค์ประกอบที่ 8 นั้นเป็นการดำเนินการที่คงที่เสมอโดยไม่คำนึงถึงขนาดอินพุต เนื่องจากโดยไม่คำนึงถึงขนาดของอินพุต (เช่น 10,100,100..) การดำเนินการ get(8) จะใช้เวลาเท่ากันเสมอ นอกจากนี้ เนื่องจากเราทราบแน่นอนว่า n > 8 จึงไม่มีโอกาสที่การพยายามดึงองค์ประกอบที่ 8 จะส่งผลให้มีขนาดเกินขนาดของอินพุต

person attaboy182    schedule 18.05.2016
comment
O(1) ไม่ได้หมายความถึงเวลาทำงานคงที่ และเวลาไม่ได้ขึ้นอยู่กับขนาดอินพุต แต่มันบอกเป็นนัยว่าเวลาทำงานถูกจำกัดด้วยค่าคงที่ - person Paul Hankin; 19.05.2016
comment
@PaulHankin ประเด็นทั้งหมดพยายามทำให้คนเข้าใจ O(1) มีเหตุผลที่ผมใช้คำว่าบอกเป็นนัย - person attaboy182; 19.05.2016
comment
แน่นอน แต่มีความเข้าใจผิดมากมายเกี่ยวกับ big-O และความซับซ้อน และฉันไม่คิดว่าคำตอบที่ดีจำเป็นต้องมีข้อผิดพลาด บางที: O(1) หมายความว่าโปรแกรมจะไม่ใช้เวลาเกินระยะเวลาที่กำหนด ไม่ว่าอินพุตจะเป็นอย่างไรก็ตาม - person Paul Hankin; 19.05.2016