Big-O ਦੱਸਦਾ ਹੈ ਕਿ ਇੱਕ algorithm ਦਾ ਚਲਾਉਣ ਦਾ ਸਮਾਂ ਜਾਂ memory ਕਿਵੇਂ ਵਧਦਾ ਹੈ ਜਦੋਂ ਇਨਪੁਟ ਆਕਾਰ n ਵਧਦਾ ਹੈ। ਇਹ worst-case asymptotic ਵਿਵਹਾਰ ਨੂੰ ਫੜਦਾ ਹੈ, constants ਅਤੇ lower-order terms ਨੂੰ ਨਜ਼ਰਅੰਦਾਜ਼ ਕਰਦਿਆਂ।
ਅਸੀਂ growth rate ਬਾਰੇ ਸੋਚਦੇ ਹਾਂ, exact step counts ਬਾਰੇ ਨਹੀਂ। O(2n + 5) ਸਿਰਫ਼ O(n) ਹੈ ਕਿਉਂਕਿ ਜਿਵੇਂ n ਵੱਡਾ ਹੁੰਦਾ ਜਾਂਦਾ ਹੈ, constants ਅਤੇ ਛੋਟੀਆਂ terms ਮਹੱਤਵਪੂਰਨ ਨਹੀਂ ਰਹਿ ਜਾਂਦੀਆਂ।
| Big-O | ਨਾਮ | ਉਦਾਹਰਨ |
|---|
| O(1) | constant | array index lookup |
| O(log n) | logarithmic | binary search |
| O(n) | linear | ਇੱਕ list ਨੂੰ ਸਕੈਨ ਕਰਨਾ |
| O(n log n) | linearithmic | merge sort |
| O(n²) | quadratic | nested loops |
| O(2ⁿ) | exponential | naive subsets |
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 constants ਨੂੰ ਲੁਕਾਉਂਦਾ ਹੈ: ਇੱਕ ਵੱਡੇ constant ਵਾਲਾ O(n) algorithm ਛੋਟੇ inputs ਉੱਤੇ O(n log n) ਦੀ ਨਿਸਬਤ ਹਾਰ ਸਕਦਾ ਹੈ। space complexity ਨੂੰ ਵੀ ਟਰੈਕ ਕਰੋ, ਸਿਰਫ਼ time ਹੀ ਨਹੀਂ।
Big-O ਤੁਹਾਨੂੰ algorithms ਦੀ ਤੁਲਨਾ ਕਰਨ ਦਿੰਦਾ ਹੈ ਉਹਨਾਂ ਨੂੰ ਚਲਾਏ ਬਿਨਾਂ ਜਾਂ hardware ਬਾਰੇ ਫਿਕਰ ਕੀਤੇ ਬਿਨਾਂ।
ਇਹ ਭਵਿੱਖਬਾਣੀ ਕਰਦਾ ਹੈ ਕਿ ਕਿਹੜੇ ਹੱਲ ਬਚਦੇ ਹਨ ਜਦੋਂ inputs ਸੌ ਤੋਂ ਮਿਲੀਅਨ ਤਕ ਵਧਦੇ ਹਨ — ਇੱਕ feature ਦੇ ਵਿਚਕਾਰ ਫਰਕ ਜੋ scale ਕਰਦਾ ਹੈ ਅਤੇ ਇੱਕ ਜੋ timeout ਹੁੰਦਾ ਹੈ।
ਇਹ vocabulary ਹੈ ਜੋ ਹਰੇਕ engineer performance ਬਾਰੇ ਤਰਕ ਕਰਨ ਲਈ ਵਰਤਦਾ ਹੈ।