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

İkili arama girdisinden ne gerektirir?

1. ADizinin 1000'den fazla eleman içermemesini
2. BDizi uzunluğunun ikinin kuvveti olmasını
3. CDizinin sıralı olmasını
4. DDizinin yalnızca pozitif sayılar içermesini

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

1. A8 saniye
2. B4 saniye
3. C1 saniye
4. D2 saniye

Memoizasyon nedir?

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

Birçok kütüphane sıralama rutini çok küçük alt diziler için neden eklemeli sıralamaya geçer?

1. AÖzyinelemeli algoritmalar 10 elemandan küçük dizileri işleyemez
2. BEklemeli sıralama en kötü durumda O(n log n)'dir
3. CEklemeli sıralamanın ek yükü azdır ve küçük veya neredeyse sıralı girdilerde hızlıdır
4. DEklemeli sıralama büyük girdilerde diğer tüm sıralama algoritmalarından daha az bellek kullanır

n elemanlı bir diziyi bir kez sıralıyor ve ardından k üyelik sorgusunu ikili aramayla yanıtlıyorsunuz. Toplam maliyet nedir?

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

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(n)
3. CO(log n)
4. DO(n²)

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

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

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. AEn fazla minimumun log n katıdır
2. BHer zaman minimum bir düğüm örtüsüdür
3. CEn fazla minimum düğüm örtüsünün iki katı büyüklüğündedir
4. DOptimuma kıyasla kalitesi bilinmez