10. Sınıf Cebirsel ve Fonksiyonel İşlemlerin Algoritmik Yapısı Test 1

Bir fonksiyonun algoritmik karmaşıklığı \(O(n^2)\) olarak verilmiştir. Bu fonksiyon 1000 elemanlı bir girdi için 10 ms sürede çalışıyorsa, 3000 elemanlı girdi için tahmini çalışma süresi ne olur?

A) 30 ms
B) 90 ms
C) 900 ms
D) 9000 ms

Bu soruda, bir algoritmanın çalışma süresinin, girdi boyutuna göre nasıl değiştiğini anlamamız gerekiyor. Algoritmik karmaşıklık, bir algoritmanın performansını girdi boyutu ($n$) arttıkça nasıl ölçeklendiğini gösteren önemli bir kavramdır. Şimdi adım adım bu soruyu çözelim:

• Algoritmik Karmaşıklığın Anlamı: Soruda fonksiyonun algoritmik karmaşıklığı $O(n^2)$ olarak verilmiş. Bu ifade, fonksiyonun çalışma süresinin (yaklaşık olarak) girdi eleman sayısının ($n$) karesiyle doğru orantılı olduğunu gösterir. Yani, çalışma süresi $T(n)$ için $T(n) \approx c \cdot n^2$ şeklinde bir ilişki kurabiliriz, burada $c$ bir sabittir.
• Verilen Bilgileri Not Edelim:

  İlk girdi eleman sayısı ($n_1$): $1000$

  $1000$ elemanlı girdi için çalışma süresi ($T_1$): $10$ ms

  İkinci girdi eleman sayısı ($n_2$): $3000$

  $3000$ elemanlı girdi için tahmini çalışma süresi ($T_2$): ?

• Orantı Kurma:

  Algoritmanın çalışma süresi $T(n) = c \cdot n^2$ formülüne uyduğu için, iki farklı girdi boyutu için aşağıdaki orantıyı yazabiliriz:

  $T_1 = c \cdot n_1^2$

  $T_2 = c \cdot n_2^2$

  Bu iki denklemi birbirine oranlarsak, $c$ sabitini ortadan kaldırabiliriz:

  $\frac{T_2}{T_1} = \frac{c \cdot n_2^2}{c \cdot n_1^2}$

  $\frac{T_2}{T_1} = \frac{n_2^2}{n_1^2}$

  Bu ifadeyi daha anlaşılır hale getirelim:

  $\frac{T_2}{T_1} = \left(\frac{n_2}{n_1}\right)^2$

  Şimdi $T_2$'yi bulmak için formülü düzenleyelim:

  $T_2 = T_1 \cdot \left(\frac{n_2}{n_1}\right)^2$

• Değerleri Yerine Koyma ve Hesaplama:

  Şimdi verilen değerleri formülümüze yerleştirelim:

  $n_1 = 1000$

  $T_1 = 10 \text{ ms}$

  $n_2 = 3000$

  Öncelikle girdi boyutlarının oranını bulalım:

  $\frac{n_2}{n_1} = \frac{3000}{1000} = 3$

  Şimdi bu oranın karesini alalım:

  $\left(\frac{n_2}{n_1}\right)^2 = 3^2 = 9$

  Son olarak, $T_2$'yi hesaplayalım:

  $T_2 = 10 \text{ ms} \cdot 9$

  $T_2 = 90 \text{ ms}$

Bu durumda, 3000 elemanlı bir girdi için tahmini çalışma süresi 90 ms olacaktır.

Cevap B seçeneğidir.