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

Zaten sıralı bir dizide eklemeli sıralamanın en iyi durum zaman karmaşıklığı nedir?

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

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

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

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

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

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(k n log n)
2. BO(nk)
3. CO(n + k)
4. DO(n log n + k log n)

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

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

Aşağıdan yukarıya bir tabloyla n. Fibonacci sayısını hesaplamanın zaman karmaşıklığı nedir?

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

Bir problem hangi durumda NP-tamdır?

1. ANP'nin dışındadır ama durma problemi gibi tüm NP problemlerinden daha zordur
2. BÇözülmesi imkânsızdır
3. CPolinom zamanda çözülebilir
4. DNP'dedir ve her NP problemi ona polinom zamanda indirgenebilir

Held–Karp dinamik programlama algoritması gezgin satıcı problemini tam olarak çözer. n şehir için çalışma süresi nedir?

1. AO(n² 2ⁿ)
2. BO(n!)
3. CO(2^n²)
4. DO(n³)