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

Özyineleme nedir?

1. ABir sıralama yöntemi
2. BHiç bitmeyen bir döngü
3. CKendisini daha küçük girdilerle çağıran bir fonksiyon
4. DBir veri yapısı türü

n elemanlı sırasız bir dizide doğrusal aramanın zaman karmaşıklığı (en kötü durumda) nedir?

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

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

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

V düğümlü ve E kenarlı bir çizgede Bellman–Ford algoritmasının zaman karmaşıklığı nedir?

1. AO(V³ × E)
2. BO(E log V)
3. CO(V × E)
4. DO(V + E)

İki n × n matrisi standart üçlü döngüyle çarpmanın zaman karmaşıklığı nedir?

1. AO(n² log n)
2. BO(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(m + n)
2. BO(mn log n)
3. CO(2^m+n)
4. DO(mn)

Büyük n için n! ve 2ⁿ nasıl karşılaştırılır?

1. An!, 2ⁿ'den daha hızlı büyür
2. B2ⁿ, n!'den daha hızlı büyür
3. CAynı hızda büyürler
4. Dn!, O(n²)'dir

Strassen algoritması matrisleri yarı boyutlu blokların 8 yerine 7 özyinelemeli çarpımını kullanarak çarpar. Çalışma süresi nedir?

1. AΘ(n² log n)
2. BΘ(n³)
3. CΘ(n²)
4. DΘ(n^{log₂ 7}), yaklaşık n^2,81