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

0 ile k aralığındaki n tamsayı için sayma sıralamasının (counting sort) çalışma süresi nedir?

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

Bir işlemin O(1) zamanda çalışması ne anlama gelir?

1. AÇalışma süresinin saniyesi başına tam olarak bir eleman işler
2. BHer zaman tam olarak bir saniye sürer
3. CÇalışma süresi girdi boyutuyla büyümez
4. DYalnızca bir kez çalıştırılabilir

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

Etkinlik seçimi probleminde hangi açgözlü kural her zaman çakışmayan en fazla sayıda etkinliği verir?

1. AÖnce en az çakışması olan etkinliği seç, sonra uyumlu olanlarla tekrarla
2. BÖnce en kısa etkinliği seç
3. CEn erken biten etkinliği seç, sonra uyumlu olanlarla tekrarla
4. DEn erken başlayan etkinliği seç

Dolduğunda kapasitesini iki katına çıkaran dinamik bir dizinin sonuna eleman eklemenin amortize zaman karmaşıklığı nedir?

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

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

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

Küçük o gösterimi hakkında hangi ifade doğrudur?

1. An² = o(n)
2. Bn = o(n²)'dir, ama n, o(n) değildir
3. Cn = o(n), çünkü her fonksiyon kendisinin küçük o'sudur
4. D2n = o(n), çünkü 2n yavaş büyür

Bellman–Ford algoritması kaynaktan ulaşılabilen negatif ağırlıklı bir döngüyü nasıl tespit eder?

1. ADijkstra algoritmasını iki kez çalıştırır ve iki uzaklık sonucunu karşılaştırır
2. BHerhangi bir kenarın negatif ağırlığa sahip olup olmadığını kontrol eder
3. CDerinlik öncelikli aramayla döngüleri sayar
4. DV − 1 turdan sonra herhangi bir kenarın hâlâ gevşetilebilip gevşetilemediğini kontrol eder