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

Asimptotik Gösterimler nelerdir?

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

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

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

O(n)

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

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.

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

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

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

n3

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

Büyük O Gösterimi

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

log n

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

17

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?

O(n2)

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?

O(log N)

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

10^4

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

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.

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

n!

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;
}

O(n2)

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?

O(n)

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

n

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

nlog n

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

Büyük ? Gösterimi

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

Büyük ? Gösterimi

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?

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