İçeriğe geç

O(1) ve O(n)

Ders 2 / 5 · 4 dk

O(1) ve O(n)

Adım 1/11

Aynı liste, iki iş: tek bir slot'u oku ya da her yerde olabilecek bir değeri ara.

Fikir

O(1), girdi ne kadar büyürse büyüsün işin hiç değişmediği anlamına gelir. O(n) ise her öğeye bir kez dokunduğun anlamına gelir. Kendi kodunda bu ikisini ayırt etmek, en çabuk kazanılan karmaşıklık becerisidir.

Gerçek hayattan örnek

Otomat O(1)'dir: B4'e basarsın ve atıştırmalık düşer; makinede on ürün olsa da iki yüz ürün olsa da. Bir markayı süpermarketin bütün reyonlarında aramak ise O(n)'dir; mağaza büyüdükçe yürüyüş de uzar.

Kod

Sıra sende

Adımları doğru sıraya koy.

  1. Mevcut öğeyi hedefle karşılaştır
  2. İlk elemandan başla
  3. Tarama bitip hiçbir şey bulunamazsa False döndür
  4. Eşleşme yoksa sonraki elemana geç

Mini quiz

1 / 3

Hangi işlem O(1)'dir?