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

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

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

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. BYaklaşık n²
3. CYaklaşık n / 2
4. DYaklaşık log₂ n

O(2ⁿ) büyümeye ne ad verilir?

1. ALogaritmik
2. BPolinom
3. CÜstel
4. DDoğrusal

n elemanlı bir dizi için birleştirmeli sıralamanın özyinelemesi kaç seviyeye sahiptir?

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

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

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

Floyd–Warshall algoritması neyi ve ne kadar hızlı hesaplar?

1. AMinimum kapsayan ağacı O(E log V)'de
2. BTek bir kaynak düğümden diğer tüm düğümlere en kısa yolları O(V + E)'de
3. CTüm düğüm çiftleri arasındaki en kısa yolları O(V³)'te
4. DTopolojik sıralamayı O(V²)'de

Bir problem hangi durumda NP-tamdır?

1. APolinom zamanda çözülebilir
2. BÇözülmesi imkânsızdır
3. CNP'dedir ve her NP problemi ona polinom zamanda indirgenebilir
4. DNP'nin dışındadır ama durma problemi gibi tüm NP problemlerinden daha zordur

Dinamik programlama ile çözülen 0/1 sırt çantası problemi O(nW) zaman alır. Buna neden sözde polinom (pseudo-polynomial) denir?

1. AÇünkü algoritma rastgeleleştirilmiştir ve çalışma süresi her girdide değişir
2. BÇünkü yalnızca W = 0 için çalışır
3. CW bir sayıdır, bu yüzden süre W'yi yazmak için kullanılan bit sayısına göre üsteldir
4. DÇünkü n her zaman küçüktür