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

Her biri n kez çalışan iç içe iki döngüye sahip bir algoritma genellikle hangi karmaşıklığa sahiptir?

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

Kaba kuvvet algoritması nedir?

1. ABirçok işlemci üzerinde çalışan bir algoritma
2. BTüm olası aday çözümleri deneyen bir algoritma
3. CRastgele bir yanıt tahmin eden bir algoritma
4. DHer zaman özyineleme kullanan bir algoritma

Bir algoritmanın çalışma süresi O(n)'dir. Bu büyümeye ne ad verilir?

1. ALogaritmik
2. BDoğrusal
3. CSabit
4. DKaresel

Aşağıdan yukarıya bir tabloyla n. Fibonacci sayısını hesaplamanın zaman karmaşıklığı nedir?

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

Saf özyinelemeli Fibonacci'nin (fib(n) = fib(n−1) + fib(n−2)) zaman karmaşıklığı nedir?

1. AÜstel
2. BDoğrusal
3. CSabit
4. DLogaritmik

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

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

Maksimal bir eşleşmedeki her kenarın iki uç noktasını almak bir düğüm örtüsü verir. Bu örtü ne kadar iyidir?

1. AHer zaman minimum bir düğüm örtüsüdür
2. BEn fazla minimum düğüm örtüsünün iki katı büyüklüğündedir
3. CEn fazla minimumun log n katıdır
4. DOptimuma kıyasla kalitesi bilinmez

Karatsuba çarpması T(n) = 3T(n/2) + O(n) yinelemesini sağlar. Bunun çözümü nedir?

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