Algoritma analizi yapmak için big-Oh notasyonuna sahip olduğumuza göre, bu notasyonu kullanarak bazı basit algoritmaların çalışma sürelerini karakterize ederek bazı örnekler verelim. Ayrıca, önceki sözümüze uygun olarak, bu bölümde daha önce verilen yedi işlevin her birinin örnek bir algoritmanın çalışma süresini karakterize etmek için nasıl kullanılabileceğini aşağıda gösteriyoruz. Bu bölümde sözde kod kullanmak yerine, örneklerimiz için eksiksiz Python uygulamaları veriyoruz. Python'un liste sınıfını, bir değerler "dizisi" için doğal temsil olarak kullanıyoruz.

Sabit Zamanlı İşlemler Python liste sınıfının data adlı bir örneği verildiğinde, len(data) işlevine yapılan bir çağrı, sabit zamanda değerlendirilir. Bu çok basit bir algoritmadır çünkü list sınıfı her liste için listenin o anki uzunluğunu kaydeden bir örnek değişkeni tutar. Bu, listedeki öğelerin her birini yinelemeli olarak saymak için zaman ayırmak yerine, bu uzunluğu hemen rapor etmesine olanak tanır. Asimptotik gösterimi kullanarak, bu fonksiyonun O(1) zamanında çalıştığını söylüyoruz; yani, bu işlevin çalışma süresi listenin uzunluğundan (n) bağımsızdır. Python'un liste sınıfının bir başka merkezi davranışı, j tamsayı dizini için veri[j] sözdizimini kullanarak listenin rastgele bir öğesine erişime izin vermesidir. Python'un listeleri dizi tabanlı diziler olarak uygulandığından, bir listenin öğelerine yapılan başvurular ardışık bir bellek bloğunda saklanır. Listenin j'inci öğesi, her seferinde bir öğe listeyi yineleyerek değil, dizini doğrulayarak ve onu alttaki diziye bir uzaklık olarak kullanarak bulunabilir. Buna karşılık, bilgisayar donanımı, bellek adresine dayalı olarak bir öğeye sürekli zamanlı erişimi destekler. Bu nedenle, bir Python listesi için data[j] ifadesinin O(1) zamanında değerlendirildiğini söylüyoruz.

Bir Dizinin Maksimumunu Bulma Problemine Tekrar Dönmek Bir sonraki örneğimizde, bir dizideki en büyük değeri bulmak için max algoritması için bir O(n) çalışma süresi talep etti. Daha önceki sözdizimi verileri tutarlı olarak, başlatma O(1) zamanını kullanır. Döngü n kez yürütülür ve her yinelemede bir karşılaştırma ve muhtemelen bir atama ifadesi gerçekleştirir (döngü değişkeninin bakımının yanı sıra). Son olarak, Python'da bir dönüş deyimini harekete geçirme mekanizmasının O(1) zamanını kullandığını not ediyoruz. Bu adımları birleştirerek, max bulma işlevinin O(n) zamanda çalıştığını elde ederiz.

Maksimum Bulma Algoritmasının hakkında daha ilginç bir soru, mevcut "en büyük" değeri kaç kez güncelleyebileceğimizdir. En kötü durumda, eğer veriler bize artan sırada verilirse, en büyük değer n - 1 kez yeniden atanır. Ancak, girdi bize rastgele sırayla verilirse, tüm siparişler eşit olasılıkla verilirse; Bu durumda en büyük değeri güncellememizin beklenen sayısı ne olur? Bu soruyu cevaplamak için, döngünün bir yinelemesinde mevcut en büyüğü yalnızca mevcut eleman kendisinden önceki tüm elemanlardan daha büyükse güncellediğimize dikkat edin. Dizi bize rastgele verilirse, j'inci elemanın ilk j elemandan en büyük olma olasılığı 1/ j'dir (teklik varsayılarak). Bu nedenle, en büyüğü (başlatma dahil) güncellememizin beklenen sayısı, n'inci Harmonik sayı olarak bilinen

H_n = $\sum _{j=1}^n=1/j$ dir.

H_n'nin O(logn) olduğu ortaya çıktı. Güncellenme sayısı O(logn)'dur.

"Prefix Averages" problemi, bir dizi verildiğinde, her bir pozisyon için o pozisyondan önceki tüm öğelerin ortalamasını hesaplama görevidir. 

Örneğin, bir dizi [1, 2, 3, 4, 5] verildiğinde, "Prefix Averages" sonuçları [1, 1.5, 2, 2.5, 3] olacaktır.

Bu problem genellikle algoritma tasarımı ve karmaşıklık analizi eğitiminde kullanılır. Bu özellikle doğru, çünkü bu problemi çözmenin birden çok yolu vardır, ancak bu yöntemlerin her birinin farklı zaman karmaşıklıkları vardır.

İki genel yaklaşım vardır:

1. Kaba kuvvet çözümü: Her bir pozisyon için, önceki tüm öğelerin ortalamasını hesaplayın. Bu, her bir konum için O(n) işlem gerektirir, bu da algoritmanın toplam karmaşıklığını O(n^2) yapar.

2. Optimize edilmiş çözüm: Diziyi bir kez tarayın, her pozisyonda toplamı ve ortalama değeri güncelleyin. Ortalama, toplamı o pozisyona kadar olan öğe sayısına bölerek hesaplanır. Bu yaklaşım, her konumu için sabit zaman gerektirir, bu da toplam karmaşıklığı O(n) yapar.

Bu, algoritma tasarımı ve analizinde genellikle gördüğümüz bir durumdur - bir problemin naif bir çözümü genellikle daha az verimli olabilir, ve bu problemi daha dikkatli bir şekilde düşünmek ve optimizasyonlar yapmak, daha verimli bir çözüm bulmamızı sağlar. "Prefix Averages" problemi, bu durumu göstermek için güzel bir örnektir.