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

O(n²) bir algoritma n = 1000 için 1 saniye sürüyor. n = 2000 için yaklaşık ne kadar sürer?

1. A1 saniye
2. B4 saniye
3. C2 saniye
4. D8 saniye

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

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

Memoizasyon nedir?

1. AÖzyinelemeyi, çağrı yığınına gerek kalmayacak biçimde eşdeğer bir döngüye otomatik olarak dönüştürmek
2. BBir fonksiyon döndükten sonra belleği serbest bırakmak
3. CFonksiyon çağrılarının sonuçlarını saklayarak tekrarlanan çağrıları bellekten yanıtlamak
4. DHer kod satırının yanına yorum yazmak

Dinamik programlama birleştirmeli sıralama için neden gerçek bir hızlanma sağlamaz?

1. ABirleştirmeli sıralamanın özyinelemeli bir yapısı yoktur
2. BAlt problemleri çakışmaz, bu yüzden yeniden kullanılacak bir şey yoktur
3. CDinamik programlama yalnızca graf problemlerinde çalışır, dizilerde çalışmaz
4. DBirleştirmeli sıralama zaten O(n)'dir

Bir fonksiyon n yinelemeli bir döngü, ardından ayrı olarak n yinelemeli başka bir döngü çalıştırıyor. Zaman karmaşıklığı nedir?

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

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

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

Durma problemi neyi gösterir?

1. AHer program eninde sonunda durur
2. BBazı programlar daha hızlı bilgisayarlarda daha hızlı çalışır, bu yüzden durma donanıma bağlıdır
3. CHiçbir algoritma her program ve girdi için programın durup durmayacağına karar veremez
4. DDöngülerden kaçınılmalıdır

Bazı kenar ağırlıkları negatif olduğunda Dijkstra algoritması neden yanlış sonuçlar verebilir?

1. AYalnızca yönsüz çizgelerde çalışır
2. BNegatif sayılar bir öncelik kuyruğunda saklanamaz
3. CBir düğüm çıkarıldığında kesinleşir, ama sonraki bir negatif kenar ona yine de daha kısa bir yol verebilir
4. DHer negatif kenarda sonsuz döngüye girer