En iyi ve en kötü durum

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.

Örnek çözümü göster

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))

Kendini test et

En iyi ve en kötü durum: kavramları eşleştir

En iyi

1 karşılaştırma
En kötü

n karşılaştırma
Ortalama

n/2 karşılaştırma
Bulunamadı

-1 döner
Ortalama durum kaç karşılaştırma yapar?
- n
- n/2
- 1
- n^2
Cevabı göster

n — Ortalama durum n/2 karşılaştırma yapar.

En iyi durum

Hedef ilk elemandaysa ____ karşılaştırma yapılır.

Cevabı göster

Hedef ilk elemandaysa 1 karşılaştırma yapılır.

Sıradaki ders: Özet - Doğrusal arama

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler