9. Sınıf Tüketme Yaklaşımı ve Kadane Algoritmasını Karşılaştırma Nedir? Test 1

1000 elemanlı bir dizi için maksimum alt dizi toplamını bulmak isteyen bir programcı, Tüketme Yaklaşımı kullanırsa yaklaşık kaç işlem yapar?

A) 1000
B) 500.000
C) 1.000.000
D) 100.000

Merhaba sevgili öğrenciler,

Bu soruda, 1000 elemanlı bir dizi için maksimum alt dizi toplamını bulmak amacıyla "Tüketme Yaklaşımı" (Brute Force veya Exhaustive Search) kullanıldığında yaklaşık kaç işlem yapılacağını bulmamız isteniyor. Tüketme Yaklaşımı, olası tüm durumları tek tek kontrol ederek sonuca ulaşmaya çalışan bir yöntemdir.

• 1. Maksimum Alt Dizi Toplamı Problemini Anlamak:

  Bir dizideki maksimum alt dizi toplamı problemi, verilen bir dizinin ardışık elemanlarından oluşan bir alt dizinin (subarray) toplamının mümkün olan en büyük değeri bulmaktır. Örneğin, [-2, 1, -3, 4, -1, 2, 1, -5, 4] dizisi için maksimum alt dizi [4, -1, 2, 1] olup toplamı 6'dır.

• 2. Tüketme Yaklaşımı (Brute Force) Nasıl Çalışır?:

  Tüketme Yaklaşımı, bu problemi çözmek için tüm olası alt dizileri oluşturur, her birinin toplamını hesaplar ve bu toplamlar arasında en büyüğünü bulur. Bir dizinin tüm alt dizilerini oluşturmak için iki ana döngüye ihtiyacımız vardır:

  • İlk döngü (i), alt dizinin başlangıç noktasını belirler. Bu, dizinin ilk elemanından son elemanına kadar gidebilir.
  • İkinci döngü (j), alt dizinin bitiş noktasını belirler. Bu, başlangıç noktasından (i) dizinin son elemanına kadar gidebilir.

  Bu iki döngü, dizideki tüm olası alt dizileri tanımlar. Örneğin, [A, B, C] dizisi için alt diziler şunlardır:

  • [A]
  • [A, B]
  • [A, B, C]
  • [B]
  • [B, C]
  • [C]
• 3. İşlem Sayısını Hesaplama:

  Her bir alt dizinin toplamını hesaplamak için, başlangıç noktası i ve bitiş noktası j arasında kalan elemanları toplamamız gerekir. En basit Tüketme Yaklaşımı (Brute Force) çözümünde, bu toplama işlemi için üçüncü bir döngü (k) kullanılır. Bu durumda karmaşıklık $O(N^3)$ olurdu.

  Ancak, daha verimli bir Tüketme Yaklaşımı (ve genellikle "Brute Force" denildiğinde kastedilen), ikinci döngü içinde alt dizinin toplamını dinamik olarak güncellemektir. Yani, arr[i...j] alt dizisinin toplamını bulmak için arr[i...j-1] alt dizisinin toplamına sadece arr[j] elemanını ekleriz. Bu, her alt dizi toplamını $O(1)$ zamanda hesaplamamızı sağlar.

  Bu durumda, işlem sayısı şu şekilde hesaplanır:

  • Dış döngü (i): $N$ kez çalışır (dizinin ilk elemanından son elemanına kadar).
  • İç döngü (j): Her bir i değeri için, j, i'den $N-1$'e kadar çalışır.

  Toplam işlem sayısı (her bir alt dizinin başlangıç ve bitiş noktası kombinasyonu için bir toplama ve bir karşılaştırma işlemi):

  • i = 0 iken, j $N$ kez çalışır.
  • i = 1 iken, j $N-1$ kez çalışır.
  • ...
  • i = N-1 iken, j $1$ kez çalışır.

  Bu, $1 + 2 + ... + (N-1) + N$ şeklinde bir aritmetik dizinin toplamıdır. Bu toplamın formülü $N(N+1)/2$'dir.

• 4. N=1000 İçin Hesaplama:

  Dizi eleman sayısı $N = 1000$ olduğuna göre, yaklaşık işlem sayısı:

  $ \text{İşlem Sayısı} = \frac{N(N+1)}{2} $

  $ \text{İşlem Sayısı} = \frac{1000 \times (1000+1)}{2} $

  $ \text{İşlem Sayısı} = \frac{1000 \times 1001}{2} $

  $ \text{İşlem Sayısı} = 500 \times 1001 $

  $ \text{İşlem Sayısı} = 500.500 $

• 5. Sonucu Seçeneklerle Karşılaştırma:

  Hesapladığımız 500.500 değeri, seçenekler arasında B) 500.000 değerine en yakın olanıdır.

Cevap B seçeneğidir.