Big-O हे वर्णन करते की इनपुट आकार n वाढल्यावर अल्गोरिदमचा रन टाइम किंवा मेमरी कसा वाढतो. ते सर्वात वाईट प्रकरण असिम्पटोटिक वर्तन कॅप्चर करते, स्थिरांक आणि निम्न-क्रम अटींकडे दुर्लक्ष्य करते.
आपल्याला वृद्धीचा दर महत्वाचा आहे, अचूक पायरीची संख्या नाही. O(2n + 5) हे फक्त O(n) आहे कारण जसे n मोठा होतो, स्थिरांक आणि लहान अटी महत्त्वाचे होऊ शकत नाहीत.
| Big-O | नाव | उदाहरण |
|---|
| O(1) | स्थिर | अ्ले इंडेक्स लुकअप |
| O(log n) | लॉगरिदमिक | बायनरी सर्च |
| O(n) | रेखीय | यादी स्कॅन करणे |
| O(n log n) | रेखीयरिदमिक | मर्ज सॉर्ट |
| O(n²) | द्विघात | नेस्टेड लूप्स |
| O(2ⁿ) | घातांक | भोळे सबसेट्स |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
Big-O स्थिरांक लपवते: एक मोठे स्थिरांक असलेला O(n) अल्गोरिदम लहान इनपुटवर O(n log n) ला हरवू शकतो. तसेच स्पेस जटिलता ट्रॅक करा, केवळ वेळ नाही.
Big-O आपल्याला अल्गोरिदम चलवल्याशिवाय किंवा हार्डवेअरची चिंता न करता तुलना करू देते.
ते असे भाकित करते की कोणत्या सोल्यूशन्स जिवंत राहतात जेव्हा इनपुट शेकडो ते लाखो पर्यंत वाढते — एक वैशिष्ट्य ज्या स्केल करते आणि एक जो टाइमआउट होते यामध्ये फरक.
हे शब्दकोष आहे ज्या प्रत्येक इंजिनियर कार्यक्षमतेचा विचार करण्यासाठी वापरतो.