लिंक ऑर्डरबी() के समय की जटिलता क्या है। फिर() विधि अनुक्रम?

Question

मैं अपनी परियोजनाओं में लिंक और लैम्ब्डा ऑपरेशंस का उपयोग कर रहा हूं और मुझे कक्षा के दो गुणों के अनुसार सूची को क्रमबद्ध करने की आवश्यकता है। इसलिए, मैं इस्तेमाल किया OrderBy() ThenBy() के रूप में नीचे दी गई विधियों:।

class ValueWithIndex{ 
    public long Value; 
    public int Index; 
} 
... 

List<ValueWithIndex> valuesWithIndex = new List<ValueWithIndex>(); 

for (int i = 0; i < A.Length; i++){ 
    ValueWithIndex vi = new ValueWithIndex(); 
    vi.Value = A[i]; 
    vi.Index = i; 
    valuesWithIndex.Add(vi); 
} 
var orderedValues = valuesWithIndex.OrderBy(v => v.Value).ThenBy(v => v.Index); 

... 

This जवाब में, यह समझाया गया है कि, OrderBy() quicksort का उपयोग करता है, तो भले ही यह हे है (N * logn) औसत समय जटिलता, सबसे खराब मामले के लिए, समय जटिलता ओ (एन) के आसपास है। यदि ThenBy() विधि में ओ (एन) की सबसे खराब समय जटिलता है, तो इन तरीकों का उपयोग करना व्यर्थ होगा।

क्या है() विधि Quicksort का भी उपयोग करती है? यदि हां, तो इसका मतलब यह है कि उसी "v.Value" के लिए, "v.Index" es को O (N) के साथ क्रमबद्ध किया गया है? सबसे खराब समय जटिलता?

Answer 1

LINQ OrderBy(...).ThenBy(...)...ThenBy(...) विधि श्रृंखला कई प्रकार कुंजी (बहु कुंजी comparer का प्रयोग करके) द्वारा एक एकल तरह आपरेशन के रूप में।

इस प्रकार, कितने ThenBy(Descending) तरीकों कर की परवाह किए बिना आप श्रृंखला में, प्रकार आपरेशन के समय जटिलता quicksort हे (एन * logn) औसत/हे (एन) सबसे खराब स्थिति के लिए विशिष्ट रहता है शामिल हैं। निश्चित रूप से आप जो अधिक कुंजी जोड़ते हैं, दो वस्तुओं की तुलना में अधिक समय लगेगा, लेकिन सॉर्ट ऑपरेशन की जटिलता नहीं बदलेगी।