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

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

1. ADoğrusal
2. BSabit
3. CLogaritmik
4. DKaresel

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

1. A9 saniye
2. B3 saniye
3. C12 saniye
4. D6 saniye

n sayıdan oluşan sırasız bir dizide en büyük değeri bulmanın zaman karmaşıklığı nedir?

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

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

1. AEklemeli sıralama büyük girdilerde diğer tüm sıralama algoritmalarından daha az bellek kullanır
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. DÖzyinelemeli algoritmalar 10 elemandan küçük dizileri işleyemez

Etkinlik seçimi probleminde hangi açgözlü kural her zaman çakışmayan en fazla sayıda etkinliği verir?

1. AEn erken biten etkinliği seç, sonra uyumlu olanlarla tekrarla
2. BÖnce en az çakışması olan etkinliği seç, sonra uyumlu olanlarla tekrarla
3. CEn erken başlayan etkinliği seç
4. DÖnce en kısa etkinliği seç

Şunun zaman karmaşıklığı nedir: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Ana teorem (master theorem) kullanılarak T(n) = 8T(n/2) + O(n²) bağıntısının çözümü nedir?

1. AΘ(n log n)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n³)

Hangi teknik, hızlı sıralama için her girdide beklenen O(n log n) çalışma süresini sağlar?

1. AHızlı sıralamayı çalıştırmadan önce girdiyi sıralamak
2. BPivotu düzgün dağılımla rastgele seçmek
3. CÖzyinelemeyi yalnızca sol tarafta kullanmak
4. DHer zaman ilk elemanı seçmek