ความซับซ้อนของเวลาในการสำรวจอาร์เรย์

ด้านล่างนี้เป็นสองวิธีที่ฉันสามารถสำรวจอาร์เรย์ใดก็ได้:

  1. การใช้ for loop ตัวแปรจะเคลื่อนที่จากจุดเริ่มต้นไปยังจุดสิ้นสุดของอาร์เรย์
  2. การใช้ while ตัวแปรลูป 2 จะเคลื่อนที่จากทิศทางตรงกันข้ามและมาบรรจบกันในระหว่างนั้น

ความซับซ้อนของเวลาจะแตกต่างกันอย่างไร มันจะลดลงในกรณีที่สองหรือจะเหมือนเดิม?


traversal time-complexity
person Adarsh Mohanty    schedule 23.08.2020    source แหล่งที่มา
comment
จะเหมือนกันในทั้งสองกรณีเนื่องจากคุณยังคงเข้าชมแต่ละองค์ประกอบอาร์เรย์เพียงครั้งเดียว   -  person Dai    schedule 23.08.2020
comment
@Dai ความซับซ้อนของเวลาลดลง 2 เท่าไม่ใช่หรือ? ความซับซ้อนของพื้นที่จะเหมือนเดิม แต่ตามทฤษฎีแล้ววิธีที่ 2 ควรใช้ O(n/2) (ไม่คำนึงถึงการปัดเศษเป็น O(n) แน่นอน)   -  person Alex.Kh    schedule 23.08.2020
comment
ลองคิดดูด้วยวิธีนี้ -› จริงๆ แล้วมันไม่ใช่การดึงองค์ประกอบที่เสียค่าใช้จ่ายใดๆ แต่เป็นสิ่งที่คุณทำกับองค์ประกอบของอาร์เรย์ที่มีค่าใช้จ่าย ค่าใช้จ่ายดังกล่าวยังคงต้องจ่ายเพียงครั้งเดียวสำหรับแต่ละองค์ประกอบ แม้ว่าคุณจะดึงองค์ประกอบสองรายการออกมาแล้วดำเนินการแยกกันก็ตาม   -  person g.d.d.c    schedule 23.08.2020
comment
@ Alex.Kh สัญกรณ์ Big-O (และความซับซ้อนของเวลาโดยทั่วไป) เกี่ยวข้องเฉพาะกับลำดับของฟังก์ชัน (อัตราการเติบโต) ดังนั้นหากคุณมีอัลกอริทึม O(1) ที่ใช้เวลา 1,000,000 ปีกับ CPU ในปัจจุบันและและอัลกอริทึมอื่นสำหรับ ปัญหาเดียวกันที่ทำงานในเวลา O(n^2) (แต่ซึ่งทำงานในเวลาเพียงไม่กี่มิลลิวินาทีเนื่องจากการเพิ่มประสิทธิภาพ CPU บางอย่างที่ทำให้การดำเนินการแต่ละอย่างมีราคาถูกมาก แต่ยังต้องเรียกใช้ n^2 ครั้ง) ซึ่งจะไม่เปลี่ยนความซับซ้อนของเวลาและล้าน อัลกอริธึม -year ยังคง ซับซ้อนน้อยกว่า ทันเวลา   -  person Dai    schedule 23.08.2020

คำตอบ (1)


arrow_upward
0
arrow_downward

แน่นอนเหมือนกัน ทั้งสองเป็น O(n) จริงๆ แล้วไม่มีทางที่จะสำรวจอาร์เรย์ได้เร็วกว่า O(n) แม้ว่าคุณจะเปลี่ยนทิศทางจากทิศทางตรงกันข้าม คุณยังคงต้องไปที่แต่ละองค์ประกอบเพียงครั้งเดียว

person haoyu wang    schedule 23.08.2020
comment
นั่นเป็นเพราะคุณไม่ได้ทำอะไรมากมายในวง ดังนั้นเวลาของวงจึงกลายเป็นส่วนที่ใช้เวลานานที่สุด แต่ในโลกแห่งความเป็นจริง คุณมักจะต้องทำการประมวลผลสำหรับแต่ละองค์ประกอบ ในกรณีนี้การวนซ้ำ while จะช่วยประหยัดเวลาได้ไม่มากนัก - person haoyu wang; 23.08.2020
comment
ที่จริงแล้วไม่มีทางที่จะสำรวจ อาร์เรย์ ได้เร็วกว่า O(n) - ฉันจะเป็นคนฉลาดที่นี่: หากเรากำลังพูดถึงอาร์เรย์ (หรือเวกเตอร์หรือสิ่งอันดับ) < b>โดยเฉพาะ ในกรณีที่ความยาว n ถูกจำกัดไว้ที่ n <= hardware-units ดังนั้น O(1) จึงมีอัลกอริธึมอยู่ (เช่น SIMD และการนำไปใช้งานใน SSE) ฉันยืนยันว่าสิ่งเหล่านี้คืออัลกอริธึม O(1) ที่แท้จริง เนื่องจาก อัตราการเติบโต ของอัลกอริธึมเป็นศูนย์ และเมื่อ n ใหญ่เกินไป อัลกอริธึมจะไม่สามารถทำงานได้อย่างแท้จริง Jus 'sayin' (ในทางปฏิบัติ SIMD ที่ใช้ในอัลกอริธึมจบลงด้วยการสนับสนุนโดยพลการ n ดังนั้นพวกมันจึงเป็น O (n) - person Dai; 23.08.2020