10. Sınıf Tema 5: Sayma, Algoritma ve Bilişim Test 1

Bir algoritmanın zaman karmaşıklığı O(2ⁿ) olarak verilmiştir. n = 10 iken işlem süresi 1 saniye ise, n = 15 iken işlem süresi yaklaşık kaç saniye olur?

A) 16
B) 32
C) 64
D) 128

Bir algoritmanın zaman karmaşıklığı, giriş boyutu (genellikle $n$ ile gösterilir) arttıkça algoritmanın çalışma süresinin nasıl değiştiğini gösterir. $O(2^n)$ karmaşıklığına sahip bir algoritma, giriş boyutu arttıkça çalışma süresinin üssel olarak arttığı anlamına gelir. Bu tür algoritmalar genellikle çok büyük $n$ değerleri için pratik değildir.

• Adım 1: Zaman Karmaşıklığı İlişkisini Kurma

  Bir algoritmanın zaman karmaşıklığı $O(2^n)$ olarak verildiğinde, bu, algoritmanın işlem süresinin ($T$) giriş boyutu ($n$) ile $2^n$ şeklinde orantılı olduğu anlamına gelir. Bu ilişkiyi matematiksel olarak aşağıdaki gibi ifade edebiliriz:

  $T(n) = k \cdot 2^n$

  Burada $k$, algoritmanın donanım, programlama dili ve diğer sabit faktörlere bağlı olan bir orantı sabitidir. Bu sabit, algoritmanın temel birim işleminin ne kadar sürdüğünü temsil eder.

• Adım 2: Orantı Sabitini ($k$) Hesaplama

  Bize $n = 10$ iken işlem süresinin $1$ saniye olduğu bilgisi verilmiştir. Bu bilgiyi kullanarak $k$ sabitini bulabiliriz:

  $T(10) = k \cdot 2^{10}$

  Verilen değerleri yerine koyarsak:

  $1 \text{ saniye} = k \cdot 1024$

  Buradan $k$ sabitini yalnız bırakırsak:

  $k = \frac{1}{1024}$ saniye/birim

  Bu $k$ sabiti, algoritmanın her bir "birim $2^n$ işlemi" için ne kadar süre harcadığını gösterir.

• Adım 3: Yeni Durum İçin İşlem Süresini Hesaplama

  Şimdi $n = 15$ iken işlem süresini hesaplamak için bulduğumuz $k$ sabitini kullanabiliriz:

  $T(15) = k \cdot 2^{15}$

  $k$ değerini yerine yazalım:

  $T(15) = \frac{1}{1024} \cdot 2^{15}$

  Bu ifadeyi basitleştirelim. Üslü sayılarda $2^{10} = 1024$ olduğunu biliyoruz. Ayrıca $2^{15}$ ifadesini $2^{10} \cdot 2^5$ şeklinde yazabiliriz:

  $T(15) = \frac{1}{2^{10}} \cdot 2^{10} \cdot 2^5$

  $2^{10}$ terimleri birbirini götürür:

  $T(15) = 2^5$

  Son olarak $2^5$ değerini hesaplayalım:

  $2^5 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 32$

  Yani, $n=15$ iken işlem süresi yaklaşık $32$ saniye olacaktır.

• Adım 4: Sonucu Değerlendirme

  Hesaplamalarımıza göre, $n=15$ iken işlem süresi yaklaşık $32$ saniye olarak bulunmuştur. Bu sonuç, verilen seçeneklerden B seçeneği ile birebir eşleşmektedir.

Cevap B seçeneğidir.