क्या एपेंड प्रक्रिया ओ (एन) का रनटाइम है?

Question

उदाहरण के लिए, OCaml में जब आप किसी आइटम n लंबाई की एक सूची के लिए जोड़कर कर रहे हैं।

x@[mylist] 

Answer 1

हाँ, OCaml में @ के क्रम O(n) है (जहां n बाईं संकार्य की लंबाई है)।

आम तौर पर एक अपरिवर्तनीय एकल लिंक्ड सूची (या उस मामले के लिए एक अपरिवर्तनीय दोगुनी जुड़ी सूची) के अंत में संलग्न होने पर हमेशा O(n) होगा।

Answer 2

सारांश में, हां।

समझाने के लिए, एक सरल (नहीं पूंछ पुनरावर्ती) संलग्न समारोह लिखा जा सकता है इस प्रकार है:

let rec (@) xs ys = 
    match xs with 
    | [] -> ys 
    | x::xs' -> x::(xs' @ ys) 

तो आंतरिक रूप से संलग्न (@) पहली सूची (xs) टूट जाती है और cons का उपयोग करता है (::) परिणामी सूची बनाने के लिए ऑपरेटर। यह वहाँ n prepending (::), जहां n पहली सूची की लंबाई है के कदम हैं कि देखने के लिए आसान है।

Answer 3

हाँ, के रूप में उल्लेख किया है, वहाँ दो कारण यह हे (एन) होना चाहिए रहे हैं:

1. आप अकेले लिंक्ड सूची के अंत है, जो हे लेता है पुनरावृति चाहिए (एन)

2. के बाद से जोड़े अपरिवर्तनीय हैं, तो आप सभी जोड़ों को पहली सूची में संलग्न करने के लिए आदेश है, जो भी हे लेता है (एन)

इससे संबंधित एक दिलचस्प विषय पूंछ पुनरावर्ती बनाम गैर-पूंछ पुनरावर्ती है में कॉपी चाहिए वा वाईएस संलग्न करने के लिए

Answer 4

आपका कोड स्निपेट आपके सवाल, जिससे पता चलता है कि तुम क्या ऑपरेटर करता है या जो ऑपरेटर का उपयोग करने के बारे में उलझन में से मेल नहीं खाता।

@ या List.append ऑपरेटर कोनकैटेनेट्स 2 सूचियों, और list1 @ list2 ओ (लंबाई (List1)) में समय लगता है और पूंछ पुनरावर्ती नहीं है। rev_append पूंछ-पुनरावर्ती है लेकिन अभी भी ओ (एन) समय में है। एक सूची में कोई आइटम जोड़ने के लिए हमेशा की तरह हालांकि :: निर्माता के साथ है, और item :: mylist हे (1) समय लगता है।