Algoritmalar Ve Programlama Dersi 5. Ünite Sorularla Öğrenelim
Algoritma Analizi
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
-
2023-2024 Bahar Dönem Sonu Sınavı Giriş Belgeleri Yayımlandı!
date_range 2 Gün önce comment 1 visibility 338
-
2023-2024 Öğretim Yılı Bahar Dönemi Ara (Vize) Sınavı Sonuçları Açıklandı!
date_range 1 Nisan 2024 Pazartesi comment 3 visibility 2848
-
2023-2024 Bahar Dönemi Ara (Vize) Sınavı Sınav Bilgilendirmesi
date_range 20 Mart 2024 Çarşamba comment 4 visibility 3375
-
2023-2024 Bahar Ara Sınavı Giriş Belgeleri Yayımlandı!
date_range 20 Mart 2024 Çarşamba comment 0 visibility 812
-
Çıkmış Soruları Gönder Para Kazan!
date_range 21 Şubat 2024 Çarşamba comment 4 visibility 1322
-
Başarı notu nedir, nasıl hesaplanıyor? Görüntüleme : 24232
-
Bütünleme sınavı neden yapılmamaktadır? Görüntüleme : 13609
-
Harf notlarının anlamları nedir? Görüntüleme : 11601
-
Akademik durum neyi ifade ediyor? Görüntüleme : 11593
-
Akademik yetersizlik uyarısı ne anlama gelmektedir? Görüntüleme : 9320