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

Bir dizide indeksle bir elemana erişmenin karmaşıklığı nedir?

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

O(2ⁿ) büyümeye ne ad verilir?

1. ALogaritmik
2. BPolinom
3. CÜstel
4. DDoğrusal

Ortalama durum çalışma süresi neyi tanımlar?

1. An boyutundaki girdilerin belirli bir dağılımı üzerinden beklenen süreyi
2. BEn iyi durum ve en kötü durum çalışma süreleri arasındaki orta değeri
3. COrtalama uzunluktaki bir girdi için süreyi
4. DEn yaygın bilgisayardaki süreyi

O(log n)'de olduğu gibi, Büyük O'da logaritmanın tabanı neden genellikle yazılmaz?

1. ABilgisayar bilimindeki tüm logaritmaların tabanı 10'dur, bu yüzden zımnen bellidir
2. BLogaritmalar her zaman tamsayılara yuvarlanır
3. CFarklı tabanlı logaritmalar yalnızca sabit bir çarpan kadar farklıdır
4. DTaban yalnızca küçük n için önemlidir

1, 3 ve 4 değerinde madeni paralarla 6 tutarı için açgözlü "önce en büyük para" yöntemi optimuma kıyasla kaç para kullanır?

1. AAçgözlü 3 para kullanır; optimum 3'tür
2. BAçgözlü 2 para kullanır; optimum 2'dir
3. CAçgözlü 4 para kullanır; optimum 3'tür
4. DAçgözlü 3 para kullanır; optimum 2'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(n)
2. BO(log n)
3. CO(n²)
4. DO(2ⁿ)

Sıralı bir dizide karşılaştırmaya dayalı her arama neden en kötü durumda Ω(log n) karşılaştırma gerektirir?

1. AHer eleman en az bir kez karşılaştırılmalıdır
2. Bİkili arama mümkün olan tek algoritmadır ve log₂ n karşılaştırma gerektirir
3. Cn olası sonucu olan bir karar ağacının derinliği en az log₂ n olmalıdır
4. DHer karşılaştırma logaritmik zaman alır

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

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