Kadane Algoritması'nın zaman karmaşıklığının O(n) olmasının nedeni nedir?
A) Diziyi sadece bir kez taraması
B) Diziyi iki kez taraması
C) Sadece yarısını taraması
D) Rastgele eleman seçmesi
Kadane Algoritması, bir dizideki en büyük toplamlı ardışık alt diziyi (contiguous subarray) bulmak için kullanılan etkili bir algoritmadır. Bu algoritmanın zaman karmaşıklığının $O(n)$ olmasının temel nedeni, diziyi sadece bir kez tarayarak tüm işlemi tamamlamasıdır.
- Zaman Karmaşıklığı Nedir? Zaman karmaşıklığı, bir algoritmanın giriş boyutu arttıkça çalışma süresinin nasıl değiştiğini gösteren bir ölçümdür. $O(n)$ karmaşıklığı, algoritmanın çalışma süresinin giriş boyutu (n) ile doğru orantılı olduğu anlamına gelir. Yani, dizi iki katına çıkarsa, algoritmanın çalışma süresi de yaklaşık olarak iki katına çıkar. Buna "doğrusal zaman" denir.
- Kadane Algoritması Nasıl Çalışır? Kadane Algoritması, diziyi baştan sona tek bir geçişte (tarama) işler. Her elemanı ziyaret ettiğinde, o ana kadar gördüğü en büyük ardışık alt dizi toplamını ve genel olarak bulduğu en büyük ardışık alt dizi toplamını günceller.
- Tek Tarama Prensibi: Algoritma, her bir eleman için sadece birkaç sabit zamanlı işlem (toplama, karşılaştırma gibi) yapar. Örneğin, mevcut elemanı `current_max` değişkenine ekler, `current_max` negatif olursa sıfırlar ve `max_so_far` değişkenini `current_max` ile karşılaştırarak günceller. Bu işlemler, dizinin boyutu ne olursa olsun her eleman için aynı sürede gerçekleşir.
- Neden $O(n)$? Dizi `n` eleman içeriyorsa ve her eleman için sabit sayıda işlem yapılıyorsa, toplam işlem sayısı $n$ çarpı sabit bir sayı olacaktır. Bu da matematiksel olarak $O(n)$ zaman karmaşıklığına denk gelir. Algoritma, tüm elemanları görmek zorunda olduğu için daha hızlı (örneğin $O(1)$ veya $O(\log n)$) olamaz, çünkü her eleman potansiyel olarak maksimum toplamın bir parçası olabilir.
- Diğer Seçeneklerin Değerlendirilmesi:
- B) Diziyi iki kez taraması: Eğer algoritma diziyi iki kez tarasaydı, zaman karmaşıklığı $O(2n)$ olurdu ki bu da yine $O(n)$ olarak ifade edilir. Ancak Kadane'nin verimliliği tek taramadan gelir.
- C) Sadece yarısını taraması: Kadane Algoritması, doğru sonucu garanti etmek için dizinin tamamını taramak zorundadır. Sadece yarısını taramak, doğru sonucu vermeyebilir.
- D) Rastgele eleman seçmesi: Kadane Algoritması rastgele eleman seçmez; diziyi sıralı bir şekilde baştan sona tarar. Rastgele seçim genellikle farklı türdeki algoritmalarla (örneğin, bazı arama veya sıralama algoritmaları) ilişkilidir ve her zaman $O(n)$ garantisi vermez.
Bu nedenle, Kadane Algoritması'nın zaman karmaşıklığının $O(n)$ olmasının temel ve en doğru nedeni, diziyi sadece bir kez taramasıdır.
Cevap A seçeneğidir.
