Programlama Ve Algoritmalar Dersi 5. Ünite Sorularla Öğrenelim

Algoritma Analizi

1. Soru

Asimptotik Gösterimler nelerdir?

Cevap

• Büyük O Gösterimi
• Büyük ? Gösterimi
• Büyük ? Gösterimi


2. Soru

int faktoriyel(int n)
{
if (n == 0)
return 1;
else
return faktoriyel(n - 1)*n;
}

faktöriyel hesabının zaman karmaşıklığı nedir?

Cevap

O(n)


3. Soru

Özyinelemeli Olmayan Algoritmaların Analizi nasıl yapılır?

Cevap

1. Problemin girdi büyüklüğünü veren parametre belirlenir.
2. Algoritmanın temel operasyonu belirlenir.
3. Temel operasyonun sadece girdi büyüklüğüne bağlı olarak mı değiştiği kontrol
edilir. Eğer başka parametrelere göre de değişiyorsa bunlar belirlenir.

4. Temel operasyon için toplam ifadesi bulunur.
5. Toplam ifadeleri için verilen standart formüller ve kurallar kullanılarak algoritmanın ait olduğu verimlilik sınıfı bulunur.


4. Soru

For döngüsünün çalışma zamanı ne kadardır?

Cevap

for döngüsünün çalışma zamanı, içerisindeki operasyonların çalışma zamanının iterasyon sayısı ile çarpımı kadardır


5. Soru

Üçüncü dereceden (kübik) hangi Temel Asimptotik Verimlilik sınıftadır?

Cevap

n3


6. Soru

(g(n)) = ?f(n): 0 ? f(n) ? cg(n), n ? n0} ne gösterimidir?

Cevap

Büyük O Gösterimi


7. Soru

Logaritmik hangi Temel Asimptotik Verimlilik sınıftadır?

Cevap

log n


8. Soru

n=10^5 olduğunda log2n ne olur?

Cevap

17


9. Soru

for (i = 0; i < n; i++)
{
m = m + i;
}
for ( i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
m = m + i;
}
}

ikinci döngünün zaman karmaşıklığı nedir?

Cevap

O(n2)


10. Soru

bool ikiliArama(int A[], int N, int eleman)
{
int orta = N / 2;
if (N <= 0)
return false;
if (key == A[orta])
return true;
else if (key < A[orta])
return ikiliArama(A, orta, eleman);
else
return ikiliArama(&A[orta + 1], N - orta - 1, eleman);
}

ikili arama algoritmasının en kötü durum çalışmasındaki zaman karmaşıklığı nedir?

Cevap

O(log N)


11. Soru

n=10^3 olduğunda nlog2n ne olur?

Cevap

10^4


12. Soru

Özyinelemeli Algoritmaların Analizi nasıl yapılır?

Cevap

1. Girdi büyüklüğünü veren parametre belirlenir.
2. Algoritmanın temel operasyonu belirlenir.
3. Girdi parametresine göre problemin temel operasyonunun çalışma sayısının değişip değişmeyeceği belirlenir.
4. Başlangıç koşulları ile birlikte algoritmanın özyinelemeli fonksiyon bağıntısı yazılır.
5. Fonksiyonların büyümesi ve toplam ifadeleri kullanılarak özyineleme bağıntısı çözülür ve zaman karmaşıklığı bulunur.


13. Soru

Faktöriyel hangi Temel Asimptotik Verimlilik sınıftadır?

Cevap

n!


14. Soru

Aşağıda verilen kod parçacığının çalışma zamanının üst sınırını (zaman karmaşıklığı)
nedir?

for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
m = m + i;
for (j = 0; j < n; j++)
m = m + j;
}

Cevap

O(n2)


15. Soru

for (i = 0; i < n; i++)
{
m = m + i;
}
for ( i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
m = m + i;
}
}

ilk döngünün zaman karmaşıklığı nedir?

Cevap

O(n)


16. Soru

Lineer hangi Temel Asimptotik Verimlilik sınıftadır?

Cevap

n


17. Soru

Yarı doğrusal hangi Temel Asimptotik Verimlilik sınıftadır?

Cevap

nlog n


18. Soru

(g(n)) = ?f(n): c1 g(n) ? f(n) ? c2 g(n), n ? n0} ne gösterimidir?

Cevap

Büyük ? Gösterimi


19. Soru

(g(n)) = ?f(n): 0 ? cg(n) ? f(n), n ? n0} ne gösterimidir?

Cevap

Büyük ? Gösterimi


20. Soru

int ToplamRecursive(int n)
{
int tmpToplam = 0;
if (n == 1) return 1;
tmpToplam = ToplamRecursive(n - 1);
return tmpToplam + n;
}

çalışma zamanı fonksiyonu nasıldır?

Cevap

T(n) =  {  1             n =1
               T(n-1)+1 n>1


Yaz Okulu Kayıt ve Ders Seçme
5 Temmuz 2021 Pazartesi