Big-O yana bayyana yadda lokacin gudu na algorithm ko ƙarfin alaƙa ya haɓaka yayin da girman input n ya haɓaka. Yana ɗauke da mafi muni asymptotic behavior, yana watsi da constants da ƙananan ƴan sharuɗi.
Mu ga kadar haɓakawa, ba daidaitan adadi ba. O(2n + 5) shine kawai O(n) saboda yayin da n ya haɓaka sosai, constants da ƙananan ƴan sharuɗi ba sa da mahimanci.
| Big-O | Suna | Misali |
|---|
| O(1) | constant | array index lookup |
| O(log n) | logarithmic | binary search |
| O(n) | linear | scanning a 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 yana ɗauke da constants: algorithm na O(n) mai babbar constant na iya kawar zuwa O(n log n) akan ƙarami inputs. Har ila yau, lura da karfi na lokaci, ba kawai lokaci ba.
Big-O yana bayar maka damar kwatanta algorithms ba tare da juyawa su ba ko damuwa game da hardware.
Yana hashe wane mafita suke tsira yayin da inputs suka ɓabbar fili daga daruruwa zuwa miliyan — bambanci tsakanin fasalin da ke haɓaka da ɗayan da ke tsaya.
Shi ne kalmomin da kowane injiniya ake amfani da shi don tunanin aiki.