Cevaplı Algoritmalar ve karmaşıklık çalışma kâğıdı

Özyinelemeli bir fonksiyonun temel durumu nedir?

1. AEn fazla bellek kullanan çağrı
2. BFonksiyonun ilk satırı
3. CEn büyük girdiye sahip durum; herhangi bir özyinelemeli çağrıdan önce ele alınır
4. DYeni bir özyinelemeli çağrı yapmadan doğrudan yanıtlanan bir durum

Birleştirmeli sıralamanın en kötü durum zaman karmaşıklığı nedir?

1. AO(log n)
2. BO(n²)
3. CO(n)
4. DO(n log n)

f(n) = Θ(g(n)) ne anlama gelir?

1. Af, g'den kesinlikle daha hızlı büyür
2. Bf, g'den kesinlikle daha yavaş büyür
3. Cf her n için her zaman g'den küçüktür, yani g onu yukarıdan sınırlar ama aşağıdan asla sınırlamaz
4. Df, g ile aynı hızda büyür; yukarıdan ve aşağıdan g'nin sabit katlarıyla sınırlıdır

Hızlı sıralamanın (quicksort) en kötü durum zaman karmaşıklığı nedir?

1. AO(n log n)
2. BO(n)
3. CO(log n)
4. DO(n²)

1, 3 ve 4 değerinde madeni paralarla 6 tutarı için açgözlü "önce en büyük para" yöntemi optimuma kıyasla kaç para kullanır?

1. AAçgözlü 3 para kullanır; optimum 2'dir
2. BAçgözlü 4 para kullanır; optimum 3'tür
3. CAçgözlü 3 para kullanır; optimum 3'tür
4. DAçgözlü 2 para kullanır; optimum 2'dir

Şunun zaman karmaşıklığı nedir: for i = 1 to n: for j = 1 to i: O(1) iş yap?

1. AO(n³)
2. BO(n²)
3. CO(n)
4. DO(n log n)

Eklemeli sıralama sıralı girdide O(n)'de çalışır. Bu, karşılaştırmalı sıralama için Ω(n log n) alt sınırıyla çelişir mi?

1. AEvet, ama yalnızca 100'den kısa diziler için
2. BHayır, alt sınır her girdiye değil, tüm girdiler üzerinden en kötü duruma uygulanır
3. CHayır, çünkü eklemeli sıralama bir karşılaştırmalı sıralama değildir
4. DEvet, dolayısıyla alt sınır yanlıştır

NP sınıfının hangi tanımı doğrudur?

1. APolinom olmayan problemler
2. BEvet yanıtları bir sertifika verildiğinde polinom zamanda doğrulanabilen karar problemleri
3. CPolinom zamanda çözülemeyen problemler
4. DHiçbir algoritmanın çözemeyeceği problemler