Big-O, giriş boyutu n büyüdükçe bir algoritmanın çalışma zamanının veya belleğinin nasıl büyüdüğünü açıklar. En kötü durum asimptotik davranışını yakalar ve sabitleri ile düşük dereceli terimleri görmezden gelir.
Büyüme hızı hakkında önemsiyoruz, kesin adım sayıları değil. O(2n + 5) basitçe O(n) olur çünkü n büyüdükçe sabitler ve daha küçük terimler önemli olmaktan çıkar.
| Big-O | Ad | Örnek |
|---|
| O(1) | sabit | dizi indeksi araması |
| O(log n) | logaritmik | ikili arama |
| O(n) | doğrusal | listenin taranması |
| O(n log n) | doğrusal-logaritmik | merge sort |
| O(n²) | kuadratik | iç içe döngüler |
| O(2ⁿ) | üstel | naif alt kümeler |
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 sabitleri gizler: büyük bir sabit içeren O(n) algoritması küçük girdilerde O(n log n)'ye yenilir. Uzay karmaşıklığını da takip edin, sadece zamanı değil.
Big-O, algoritmaları çalıştırmadan veya donanım konusunda endişelenmeden karşılaştırmanıza izin verir.
Girdiler yüzlerden milyarlara büyüdüğünde hangi çözümlerin hayatta kalacağını tahmin eder — ölçeklendirilebilen bir özellik ile zaman aşımına uğrayan bir özellik arasındaki fark.
Bu, her mühendisçinin performans hakkında akıl yürütmek için kullandığı kelime dağarcığıdır.