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

Hangi sıralama algoritması yanlış sırada olan komşu elemanların yerini tekrar tekrar değiştirir?

1. ABirleştirmeli sıralama (merge sort)
2. BKabarcık sıralaması (bubble sort)
3. CHızlı sıralama (quicksort)
4. DYığın sıralaması (heap sort)

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

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

1. A2 saniye
2. B1 saniye
3. C8 saniye
4. D4 saniye

Hızlı sıralamanın (quicksort) en kötü durum zaman karmaşıklığı nedir?

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

İki n × n matrisi standart üçlü döngüyle çarpmanın zaman karmaşıklığı nedir?

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

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

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

Eklemeli sıralama sıralı girdide O(n)'de çalışır. Bu, karşılaştırmalı sıralama için Ω(n log n) alt sınırıyla çelişir mi?

1. AHayır, çünkü eklemeli sıralama bir karşılaştırmalı sıralama değildir
2. BEvet, ama yalnızca 100'den kısa diziler için
3. CEvet, dolayısıyla alt sınır yanlıştır
4. DHayır, alt sınır her girdiye değil, tüm girdiler üzerinden en kötü duruma uygulanır

Bu sağlanabilirlik problemlerinden hangisinin polinom zamanda çözülebildiği bilinmektedir?

1. ADevre sağlanabilirliği
2. BHer yan tümcenin tam olarak üç literal içerdiği 3-SAT
3. CHer yan tümcenin en fazla iki literal içerdiği 2-SAT
4. DBirleşimli normal biçimdeki formüller üzerinde genel SAT