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

Alan karmaşıklığı neyi ölçer?

1. ABilgisayarın fiziksel boyutunu
2. BGirdi büyüdükçe bir algoritmanın ihtiyaç duyduğu bellek miktarını
3. CProgramın derlendikten sonraki dosyasının disk alanını
4. DKod satırı sayısını

Bir algoritmanın en kötü durum çalışma süresi neyi tanımlar?

1. AEn küçük girdide aldığı süreyi
2. BYavaş bir bilgisayarda aldığı süreyi
3. Cn boyutundaki rastgele bir girdide beklenen süreyi
4. Dn boyutundaki tüm girdiler üzerinden aldığı en uzun süreyi

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

1. AKaresel
2. BLogaritmik
3. CDoğrusal
4. DSabit

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

1. AÜstel
2. BLogaritmik
3. CDoğrusal
4. DSabit

Bir problemin optimal alt yapıya sahip olması ne anlama gelir?

1. AHer alt problem aynı boyuttadır
2. BProblemin tam olarak bir optimal çözümü vardır ve bu çözümü her alt problem paylaşır
3. COptimal bir çözüm, alt problemlerinin optimal çözümlerinden oluşturulabilir
4. DProblem sabit zamanda çözülebilir

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

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

2²ⁿ, O(2ⁿ) içinde midir?

1. AEvet, çünkü üsteki sabit çarpanlar Büyük O'da her zaman göz ardı edilir
2. BHayır, çünkü 2²ⁿ, 2ⁿ'den daha yavaş büyür
3. CEvet, çünkü ikisi de üsteldir
4. DHayır, çünkü 2²ⁿ = 4ⁿ ve 4ⁿ / 2ⁿ = 2ⁿ sınırsız büyür

Eklemeli sıralama sıralı girdide O(n)'de çalışır. Bu, karşılaştırmalı sıralama için Ω(n log n) alt sınırıyla çelişir mi?

1. AHayır, alt sınır her girdiye değil, tüm girdiler üzerinden en kötü duruma uygulanır
2. BEvet, ama yalnızca 100'den kısa diziler için
3. CEvet, dolayısıyla alt sınır yanlıştır
4. DHayır, çünkü eklemeli sıralama bir karşılaştırmalı sıralama değildir