ฉันมีสถานการณ์ที่ฉันมีช่วงอินพุตที่แน่นอน ดังนั้นฉันจึงสามารถจัดทำดัชนีทั้งหมดใน O(1) ได้ด้วยการสร้างรายการที่มีขนาดเท่ากับช่วงของอินพุตและจัดทำดัชนีอินพุตด้วยตัวเอง เพื่อให้ชัดเจนยิ่งขึ้น ฉันมีสถานการณ์ต่อไปนี้เป็นหลัก
a = "inputrange"
rng = ord(max(a)) - ord(min(s))
data = [None] * rng
ปัญหาของฉันคือ ฉันไม่แน่ใจว่ากระบวนการจัดสรรสำหรับ data เป็น O(1) หรือไม่ โดยสังหรณ์ใจ ควรมีวิธีการบางอย่างใน O(1) เนื่องจากในสแต็กฉันแค่กำหนดจุดเริ่มต้นและจุดสิ้นสุดสำหรับข้อมูล และด้วยเหตุนี้จึงควรใช้เวลา O(1) เท่านั้นในการจัดสรร แต่ python มันถูกลบออกไปเล็กน้อยดังนั้นฉันจึงไม่แน่ใจ
เป็นสิ่งสำคัญมากที่ฉันสามารถจัดสรรใน O(1) เนื่องจากฉันกำลังสร้างแผนผังส่วนต่อท้ายสำหรับข้อมูลอินพุต และเพื่อให้มั่นใจว่ามีการจัดทำดัชนี O(1) เมื่อสำรวจแผนภูมิ ฉันต้องการรายการขนาดของตัวอักษร (หรือแฮชแมป แม้ว่าฉันจะหลีกเลี่ยงสิ่งเหล่านั้น) แต่เนื่องจากฉันกำลังจัดสรรเป็นหลักสำหรับทุกส่วนต่อท้าย ฉันจึงต้องจัดสรรให้คงที่
แนวคิดอีกอย่างหนึ่งที่ฉันมีคือสร้างรายการเทมเพลตแล้วคัดลอกมันทับ แต่การคัดลอกต้องใช้เวลา O(n) ดังนั้นมันจะไม่ได้ผล
แก้ไข: นี่ไม่ใช่สิ่งที่ซ้ำซ้อนกับความซับซ้อนของเวลาของ [var]*n ฉัน ชัดเจน ระบุว่าฉันกำลังมองหาวิธีที่จะทำรายการการจัดสรรหน่วยความจำใน O (1) เพียงเพราะฉันใช้ [var]*n เป็นวิธีปัจจุบันในการจัดสรรหน่วยความจำนี้ ไม่ได้หมายความว่าจะได้รับคำตอบจากการรู้ความซับซ้อนของวิธีนี้
คำถามยังคงอยู่: มีวิธีจัดสรรพื้นที่สำหรับรายการว่างใน python ในเวลา O(1) หรือไม่
Noneลงในแต่ละองค์ประกอบจะเป็น O(n) - person Barmar schedule 21.04.2021listเป็นอาร์เรย์ดั้งเดิมของ C[None] * rngคือการดำเนินการเวลาเชิงเส้น แต่ไม่มีทางหลีกเลี่ยงได้ หรือพิจารณาnumpyและnumpy.empty- person juanpa.arrivillaga schedule 21.04.2021Nคือขนาดของรายการนั้น หมายเหตุ[None]*nไม่ว่างเปล่า (ยกเว้นn ==0),[]เป็นรายการว่าง[None, None, None]ไม่ - person juanpa.arrivillaga schedule 21.04.2021