En iyi ve en kötü durum
- Algoritmalar kursu
- Başlangıç
- Ders 15/80
- 4 dk
Doğrusal aramada en iyi O(1), en kötü O(n) durumları öğrenirsin.
En iyi ve en kötü durum
Doğrusal aramada en iyi durum: hedef ilk elemandır, 1 karşılaştırma, O(1). En kötü durum: hedef son elemandır veya yoktur, n karşılaştırma, O(n).
Ortalama durum: hedef dizinin ortasındadır, n/2 karşılaştırma. Big-O sabitleri yok saydığı için ortalama da O(n) yazılır.
Sıralı vs sırasız dizi
Doğrusal arama, dizinin sıralı olmasını gerektirmez. Sıralı dizilerde hedeften büyük bir eleman görünce arama durdurulabilir.
Ancak bu iyileştirme en kötü durumu değiştirmez: hedef dizide yoksa yine tüm dizi gezilir ve karmaşıklık O(n) kalır.
Uygulama İçerir mi
contains(arr, target) yaz. Hedef varsa True, yoksa False döndür. print(contains([1, 3, 5], 3)) ile True yazdır.
Başlangıç kodu
def contains(arr, target):
# Var mı kontrol etÖrnek çözüm
def contains(arr, target):
# Var mı kontrol et
for x in arr:
if x == target:
return True
return False
print(contains([1, 3, 5], 3))Beklenen çıktı
True
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 En iyi ve en kötü durum: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
En iyi |
1 karşılaştırma |
En kötü |
n karşılaştırma |
Ortalama |
n/2 karşılaştırma |
Bulunamadı |
-1 döner |
2 Ortalama durum kaç karşılaştırma yapar?
- n Doğru cevap
- n/2
- 1
- n^2
Açıklama: Ortalama durum n/2 karşılaştırma yapar.
3 En iyi durum
Hedef ilk elemandaysa ____ karşılaştırma yapılır.Hedef ilk elemandaysa 1 karşılaştırma yapılır.Açıklama: 1 doğru.