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

Bir döngü i = 1 ile başlar ve i > n olana kadar her yinelemede i'yi iki katına çıkarır. Kaç yineleme çalışır?

1. AYaklaşık n / 2
2. BYaklaşık log₂ n
3. CYaklaşık n²
4. DYaklaşık n

O(n) bir algoritma n = 1 milyon için 3 saniye sürüyor. n = 2 milyon için yaklaşık ne kadar sürer?

1. A6 saniye
2. B3 saniye
3. C9 saniye
4. D12 saniye

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, g ile aynı hızda büyür; yukarıdan ve aşağıdan g'nin sabit katlarıyla sınırlıdır
4. Df 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

Birçok kütüphane sıralama rutini çok küçük alt diziler için neden eklemeli sıralamaya geçer?

1. AEklemeli sıralamanın ek yükü azdır ve küçük veya neredeyse sıralı girdilerde hızlıdır
2. BEklemeli sıralama en kötü durumda O(n log n)'dir
3. CÖzyinelemeli algoritmalar 10 elemandan küçük dizileri işleyemez
4. DEklemeli sıralama büyük girdilerde diğer tüm sıralama algoritmalarından daha az bellek kullanır

T(n) = T(n − 1) + O(1) yinelemesinin çözümü nedir?

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

m ve n uzunluğundaki dizgilerin en uzun ortak alt dizisi için standart dinamik programlama algoritmasının zaman karmaşıklığı nedir?

1. AO(2^m+n)
2. BO(mn log n)
3. CO(m + n)
4. DO(mn)

Gezgin satıcı problemi nasıl sınıflandırılır?

1. AKarar versiyonu P'de, optimizasyon versiyonu ise NP-tamdır
2. BDijkstra algoritması her şehri bir kez ziyaret ederek onu çözdüğü için P'dedir
3. CKarar verilemezdir
4. DKarar versiyonu NP-tam, optimizasyon versiyonu NP-zordur

Aşağıdan yukarıya (bottom-up) yöntemle n sırasız elemandan ikili yığın oluşturmanın zaman karmaşıklığı nedir?

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