ALGORİTMALAR VE PROGRAMLAMA Dersi Algoritma Analizi soru cevapları:
Toplam 20 Soru & Cevap#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:
Ö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.
#3
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.
#4
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)
#5
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)
#6
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
#7
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)
#8
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)
#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:
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
#14
SORU:
Üçüncü dereceden (kübik) hangi Temel Asimptotik Verimlilik sınıftadır?
CEVAP:
n3
#16
SORU:
(g(n)) = ?f(n): c1 g(n) ? f(n) ? c2 g(n), n ? n0} ne gösterimidir?
CEVAP:
Büyük ? Gösterimi
#17
SORU:
(g(n)) = ?f(n): 0 ? cg(n) ? f(n), n ? n0} ne gösterimidir?
CEVAP:
Büyük ? Gösterimi
#18
SORU:
(g(n)) = ?f(n): 0 ? f(n) ? cg(n), n ? n0} ne gösterimidir?
CEVAP:
Büyük O Gösterimi