त्रिभुज संख्याओं के लिए बिग ओ नोटेशन?

Question

triangular समय में चलने वाले एल्गोरिदम के लिए सही बड़ा ओ नोटेशन क्या है? यहाँ एक उदाहरण है:

func(x): 
    for i in 0..x 
    for j in 0..i 
     do_something(i, j) 

मेरी पहली वृत्ति O(n²) है, लेकिन मैं पूरी तरह यकीन नहीं है।

Answer 1

हाँ, एन * (एन + 1)/2, जब आप स्थिरांक और निचले क्रम के नियम छोड़ते हैं, तो आपको एन-स्क्वायर के साथ छोड़ देता है।

Answer 2

हाँ, O(n^2) निश्चित रूप से सही है। अगर मैं सही ढंग से याद करता हूं, तो ओ हमेशा एक ऊपरी बाउंड है, इसलिए O(n^3) आईएमओ भी सही होना चाहिए, जैसा कि O(n^n) या जो कुछ भी होगा। हालांकि O(n^2) सबसे कसकर लगता है जो आसानी से कटौती योग्य है।

Answer 3

यदि आप गणितीय रूप से इसके बारे में सोचते हैं, तो त्रिकोण का क्षेत्र आप कंप्यूटिंग कर रहे हैं ((n+1)^2)/2 है। इसलिए यह कम्प्यूटेशनल समय है: ओ ((एन + 1)^2)/2)

Answer 4

गणना कोड इस कोड के लिए एन * (एन + 1)/2 के कारक द्वारा बढ़ता है। यह अनिवार्य रूप से ओ (एन^2) है।

Answer 5

जब एन से इनपुट बढ़ जाती है 2N, इसके बाद अपने एल्गोरिथ्म के समय चलने से टी 4T

इस तरह समय से चल रहा है करने के लिए वृद्धि होगी इनपुट आकार के वर्ग के समानुपाती होता है

तो एल्गोरिथ्म हे है (एन^2)

Answer 6

ओ (! एन) एक फैक्टरियल गणना (त्रिकोणीय समय) के लिए मामलों को संभालता है।

इसे ओ (एन^2) के रूप में भी प्रदर्शित किया जा सकता है, यह थोड़ा भ्रामक प्रतीत होता है क्योंकि निष्पादित की जाने वाली राशि हमेशा आधे (एन^2) के रूप में आधा हो जाएगी।