Algoritma verimliliği algoritma tarafından kullanılan hesaplama kaynaklarıyla ilişkili bir algoritmanın özelliğidir. Algoritmanın ihtiyaç duyduğu kaynakları belirlemek için algoritmanın analiz edilmesi gerekir. Algoritma verimliliği, tekrarlanan veya sürekli süreçlerin üretim verimliliğine benzer olarak düşünülebilir.

Maksimum verimliliğe ulaşmak için kaynak kullanımını azaltmak istiyoruz. Bununla birlikte, farklı kaynaklar (zaman ve bellek gibi) doğrudan karşılaştırılamaz; dolayısıyla iki algoritmadan hangisinin daha verimli olduğu genellikle yüksek hız gereksinimi, minimum bellek kullanımı veya başka bir ölçüm gibi hangi faktörün daha önemli olduğuna bağlıdır. yeterlik.

Lütfen bu makalenin OLUMSUZ program optimizasyonu, derleyiciyi optimize etme makalelerinde ele alınan algoritma optimizasyonu hakkında, döngü optimizasyonu, nesne kodu iyileştirici, ve benzeri. "Optimizasyon" teriminin kendisi yanıltıcıdır çünkü yapılabilecek her şey "iyileştirme" şemsiyesi altına girmektedir.

Arka plan

Yürütme süresine vurgu yaparak verimliliğin önemi, 1843'te Ada Lovelace tarafından Charles Babbage'ın mekanik analitik motoruyla ilgili olarak vurgulanmıştır:

"Neredeyse tüm bilgisayarlarda, süreci başarılı bir şekilde tamamlamak için mümkün olan çok sayıda yapılandırma seçeneği vardır ve hesaplamanın gerçekleştirilme amacına yönelik seçimi farklı gelenekler etkilemelidir. Önemli olan, hesaplamayı gerçekleştirmek için gereken süreyi en aza indirecek bir konfigürasyon seçmektir."

İlk elektronik bilgisayarların hem hızı hem de belleği oldukça sınırlıydı. Bazı durumlarda, bir görevin yüksek hıza ulaşmak için büyük miktarda bellek kullanması ya da az miktarda çalışma belleği kullanan daha yavaş bir algoritma kullanması gereken bir zaman-bellek değiş tokuşunun olduğu fark edilmiştir. Bu durumda, mevcut belleğin yeterli olduğu en hızlı algoritma kullanıldı.

Modern bilgisayarlar, eski bilgisayarlardan çok daha hızlıdır ve çok daha fazla belleğe sahiptir (kilobayt yerine gigabayt). Ancak Donald Knuth, verimliliğin hala önemli bir faktör olduğunu vurguluyor:

"Yerleşik mühendislik disiplinlerinde %12'lik bir iyileşme kolaylıkla başarılabilir ve hiçbir zaman engelleyici olarak düşünülmemiştir ve aynı şeyin programlama için de geçerli olması gerektiğine inanıyorum."

Gözden geçirmek

Bir algoritma, kaynak tüketimi (veya kaynak maliyeti) kabul edilebilir bir seviyede veya bunun altındaysa verimli kabul edilir. Kabaca söylemek gerekirse, burada "kabul edilebilir", "algoritmanın mevcut bir bilgisayarda makul bir süre boyunca çalışacağı" anlamına gelir. 1950'li yıllardan bu yana bilgisayarların işlem gücünde ve kullanılabilir belleğinde ciddi bir artış olduğu için mevcut "kabul edilebilir seviye" bundan 10 yıl önce bile kabul edilebilir değildi.

Bilgisayar üreticileri periyodik olarak yeni modeller, genellikle daha güçlü modeller yayınlar. Yazılımın maliyeti oldukça yüksek olabilir, dolayısıyla bazı durumlarda mevcut bilgisayarınızla uyumlu, daha hızlı bir bilgisayar satın alarak daha iyi performans elde etmek daha kolay ve daha ucuz olabilir.

Bir algoritmanın kullandığı kaynakları ölçmenin birçok yolu vardır. En çok kullanılan iki ölçüm, hız ve kullanılan hafızadır. Diğer ölçümler arasında aktarım hızı, geçici disk kullanımı, uzun süreli disk kullanımı, güç tüketimi, toplam sahip olma maliyeti, harici sinyallere yanıt süresi vb. yer alabilir. Bu ölçümlerin çoğu, algoritmanın giriş verilerinin boyutuna (yani, veri işlemeyi gerektiren miktarlara) bağlıdır. Ölçümler ayrıca verilerin sunulma şekline de bağlı olabilir (örneğin, bazı sıralama algoritmaları önceden sıralanmış veriler üzerinde veya veriler ters sırada sıralandığında kötü performans gösterir).

Uygulamada, gerekli doğruluk ve/veya güvenilirlik gibi algoritmanın etkinliğini etkileyen başka faktörler de vardır. Aşağıda açıklandığı gibi, uygulamanın birçok yönü optimizasyon sorunları olmasına rağmen, bir algoritmanın uygulanma şekli de gerçek performans üzerinde önemli bir etkiye sahip olabilir.

Teorik analiz

Algoritmaların teorik analizinde, bir algoritmanın karmaşıklığını asimptotik davranışıyla tahmin etmek, yani algoritmanın karmaşıklığını girdi boyutunun bir fonksiyonu olarak yansıtmak yaygın bir uygulamadır. N Büyük O notasyonu kullanılır. Bu tahmin genellikle büyük ölçekli şirketler için oldukça doğrudur. N ancak küçük değerlerde yanlış sonuçlara yol açabilir N(Dolayısıyla, yavaş olduğu düşünülen kabarcık sıralama, yalnızca birkaç öğeyi sıralamanız gerekiyorsa hızlı sıralamadan daha hızlı olabilir).

Tanım	İsim	Örnekler
Ç(1) (\displaystyle O(1)\,)	kalıcı	Bir sayının çift mi tek mi olduğunu belirleme. Sabit boyutlu bir arama tablosu kullanma. Bir öğeyi seçmek için uygun bir karma işlevi kullanma.
O (log ⁡ n) (\displaystyle O(\log n)\,)	logaritmik	Binom yığınındaki işlemlere benzer şekilde ikili arama veya dengeli ağaç kullanarak sıralanmış bir dizideki bir öğeyi bulma.
O(n) (\displaystyle O(n)\,)	doğrusal	Sıralanmamış bir listede veya dengesiz bir ağaçta bir öğe bulma (en kötü durum). İki eklenmesi N-bit sayıları uçtan uca taşımayı kullanır.
Ö (n log ⁡ n) (\displaystyle O(n\log n)\,)	yarı doğrusal, logaritmik olarak doğrusal	Hızlı hesaplama Fourier dönüşümü, yığın sıralama, hızlı sıralama (en iyi ve ortalama durum), birleştirme sıralaması
Ö (n 2) (\displaystyle O(n^(2))\,)	kare	İkiyi çarpmak N-basit bir algoritma kullanan basamaklı sayılar, kabarcık sıralama (en kötü durum), Kabuk sıralama, hızlı sıralama (en kötü durum), seçim sıralaması, ekleme sıralaması
Ö (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1)	üstel	Dinamik programlamayı kullanarak gezgin satıcı problemine (kesin) bir çözüm bulmak. Kapsamlı aramayı kullanarak iki mantıksal ifadenin eşdeğer olup olmadığını belirleme

Doğrulama Testleri: Performansın Ölçülmesi

Yazılımın yeni sürümleri için veya rakip sistemlerle karşılaştırma sağlamak amacıyla, bazen algoritmaların göreceli performansını karşılaştırmak için kıyaslamalar kullanılır. Örneğin yeni bir sıralama algoritması yayınlanırsa, algoritmanın bilinen veriler üzerinde en az diğerleri kadar verimli olduğundan emin olmak için öncekilerle karşılaştırılabilir. Performans testleri, kullanıcılar tarafından farklı üreticilerin ürünlerini karşılaştırmak ve işlevsellik ve performans açısından hangi ürünün gereksinimlerine en uygun olacağını değerlendirmek için kullanılabilir.

Bazı kıyaslama testleri, Roy Longbottom'un PC Benchmark Koleksiyonu gibi farklı derleme ve yorumlama dillerinin karşılaştırmalı analizini sağlar ve Bilgisayar Dili Karşılaştırmaları Oyunu Bazı programlama dillerinde tipik görevlerin uygulanmasının performansını karşılaştırır.

Uygulama sorunları

Uygulama sorunları gerçek performansı da etkileyebilir. Bu, programlama dili seçimini ve algoritmanın gerçekte kodlanma biçimini, seçilen dil için çevirmen seçimini veya kullanılan derleyici seçeneklerini ve hatta kullanılan işletim sistemini içerir. Bazı durumlarda yorumlayıcı olarak uygulanan bir dil, derleyici olarak uygulanan bir dilden önemli ölçüde daha yavaş olabilir.

Programcının kontrolü dışında zamanlamayı veya bellek kullanımını etkileyebilecek başka faktörler de vardır. Bu, veri hizalamayı, detaylandırmaçöp toplama, talimat seviyesinde paralellik ve altprogram çağırma.

Bazı işlemciler, bir işlemin birden fazla işleneni işlemesine olanak tanıyan vektör işlemlerini gerçekleştirme yeteneğine sahiptir. Bu tür özellikleri programlama veya derleme düzeyinde kullanmak kolay olabilir veya olmayabilir. Sıralı hesaplama için tasarlanan algoritmalar, paralel hesaplamaya uyum sağlamak için tamamen yeniden tasarlanmasını gerektirebilir.

Talimatların farklı şekilde uygulanabileceği, dolayısıyla bazı modellerdeki talimatların diğer modellerde nispeten daha yavaş olabileceği işlemci uyumluluğuyla ilgili başka bir sorun ortaya çıkabilir. Bu, optimizasyon derleyicisi için bir sorun olabilir.

Kaynak Kullanımının Ölçülmesi

Ölçümler genellikle girişin boyutunun bir fonksiyonu olarak ifade edilir. N.

En önemli iki boyut şunlardır:

• Zaman: Algoritmanın CPU üzerinde ne kadar zaman harcadığı.
• Hafıza: Algoritma için ne kadar çalışma belleğine (genellikle RAM) ihtiyaç duyulur. Bunun iki yönü vardır: kod için bellek miktarı ve kodun üzerinde çalıştığı veriler için bellek miktarı.

Pille çalışan bilgisayarlar (dizüstü bilgisayarlar gibi) veya çok uzun/büyük hesaplamalar (süper bilgisayarlar gibi) için farklı bir ölçüm türü ilgi çekicidir:

• Doğrudan enerji tüketimi: Bilgisayarı çalıştırmak için gereken enerji.
• Dolaylı enerji tüketimi: Soğutma, aydınlatma vb. için gereken enerji.

Bazı durumlarda daha az yaygın olan diğer ölçümlere ihtiyaç duyulur:

• Dişli boyutu: Bant genişliği sınırlayıcı faktör olabilir. Aktarılan veri miktarını azaltmak için sıkıştırma kullanılabilir. Bir grafiğin veya görselin (Google logosu gibi) görüntülenmesi onbinlerce baytın (bu durumda 48K) aktarılmasına neden olabilir. Bunu "Google" kelimesindeki altı baytın iletilmesiyle karşılaştırın.
• Harici bellek: Diskte veya başka bir harici depolama aygıtında gerekli bellek. Bu bellek geçici depolama için veya gelecekte kullanılmak üzere kullanılabilir.
• Tepki Süresi: Bu ayar özellikle bilgisayarın harici olaylara hızlı yanıt vermesi gereken gerçek zamanlı uygulamalar için önemlidir.
• Toplam sahip olma maliyeti: Tek bir algoritmanın yürütülmesi amaçlandığında parametre önemlidir.

Zaman

Teori

Bu tür bir test aynı zamanda önemli ölçüde programlama dili, derleyici ve seçeneklerinin seçimine de bağlıdır, dolayısıyla karşılaştırılan algoritmaların aynı koşullar altında uygulanması gerekir.

Hafıza

Bu bölüm, algoritmanın ihtiyaç duyduğu ana belleğin (genellikle RAM) kullanımıyla ilgilidir. Yukarıdaki zamanlama analizinde olduğu gibi, bir algoritmanın analizi tipik olarak aşağıdakileri kullanır: algoritmanın uzaysal karmaşıklığı Giriş boyutunun bir fonksiyonu olarak gerekli çalışma zamanı belleğini tahmin etmek. Sonuç genellikle "O" büyük cinsinden ifade edilir.

Bellek kullanımının dört yönü vardır:

• Algoritma kodunu saklamak için gereken bellek miktarı.
• Giriş verileri için gereken bellek miktarı.
• Herhangi bir çıktı için gereken bellek miktarı (sıralamalar gibi bazı algoritmalar sıklıkla girişi yeniden düzenler ve çıktı için ek bellek gerektirmez).
• Hesaplama sırasında hesaplama sürecinin gerektirdiği bellek miktarı (bu, özyineleme kullanıldığında önemli olabilecek, adlandırılmış değişkenleri ve alt rutin çağrıları için gereken yığın alanını içerir).

İlk elektronik bilgisayarlar ve ev bilgisayarları nispeten küçük işleyen bellek kapasitelerine sahipti. Böylece, 1949'da EDSAC'ın maksimum 1024 17 bit kelimelik çalışma belleği vardı ve 1980'de 1024 baytlık çalışma belleğiyle Sinclair ZX80 piyasaya sürüldü.

Modern bilgisayarlar nispeten büyük miktarda belleğe (belki de gigabayt) sahip olabilir, bu nedenle bir algoritma tarafından kullanılan belleğin belirli bir miktardaki belleğe sıkıştırılması eskisinden daha az gereklidir. Ancak üç farklı hafıza kategorisinin varlığı önemlidir:

• Önbellek (genellikle statik RAM) - CPU ile karşılaştırılabilir hızlarda çalışır
• Ana fiziksel bellek (genellikle dinamik RAM) - CPU'dan biraz daha yavaş çalışır
• Sanal bellek (genellikle diskte) - büyük bellek yanılsaması verir, ancak RAM'den binlerce kat daha yavaş çalışır.

Gerekli belleği bilgisayarın önbelleğine sığdıran bir algoritma, ana belleğe sığan bir algoritmadan çok daha hızlıdır ve bu da sanal alan kullanan bir algoritmadan çok daha hızlı olacaktır. İşleri karmaşık hale getiren şey, bazı sistemlerin üç seviyeye kadar önbelleğe sahip olmasıdır. Farklı sistemlerde bu tür belleklerin farklı miktarları vardır, dolayısıyla bir algoritma üzerindeki belleğin etkisi bir sistemden diğerine önemli ölçüde değişebilir.

Elektronik hesaplamanın ilk zamanlarında, eğer bir algoritma ve ona ait veriler ana belleğe sığmıyorsa kullanılamıyordu. Günümüzde sanal bellek kullanmak çok büyük bellek sağlıyor ancak performanstan ödün veriyor. Algoritma ve verileri önbelleğe sığarsa çok yüksek hızlara ulaşılabilir; böylece gerekli belleğin en aza indirilmesi, zamanın en aza indirilmesine yardımcı olur. Tamamen önbelleğe sığmayan ancak şunları sağlayan bir algoritma bağlantıların konumu nispeten hızlı çalışabilir.

Etkili algoritma örnekleri

Programlamanın mevcut durumunun eleştirisi

Programlar, bilgisayarların hızlanmasından daha hızlı bir şekilde yavaşlıyor.

May şunları söylüyor:

Yaygın sistemlerde, talimat yürütmenin yarıya indirilmesi pil ömrünü iki katına çıkarabilir ve büyük veriler daha iyi algoritmalar için bir fırsat sağlar: İşlem sayısını N x N'den N x log(N)'ye düşürmek, büyük N için güçlü bir etkiye sahiptir... N için =30 milyar, bu değişimler 50 yıllık teknolojik gelişmelere benzer.

En iyi algoritma için rekabet

Aşağıdaki yarışmalar, kalite kriterleri jüri tarafından belirlenen en iyi algoritmaların geliştirilmesine katılımı davet etmektedir:

Ayrıca bakınız

• Aritmetik kodlama bir tür entropi kodlamasıdır değişken kod uzunluğunda verimli veri sıkıştırma için
• İlişkisel dizi, kullanıldığında daha verimli hale getirilebilecek bir veri yapısıdır ağaçlar PATRICIA veya Judy dizileri
• Performans testi - belirli durumlarda karşılaştırmalı yürütme süresini ölçmeye yönelik bir yöntem
• En iyi, en kötü ve ortalama durum- üç senaryo için yürütme süresini tahmin etmeye yönelik kurallar
• İkili arama, sıralanmış bir listede arama yapmak için basit ve etkili bir tekniktir
• Şube tablosu

Dersin amaçları ve hedefleri: algoritmaların ve veri yapılarının karmaşıklığını ve verimliliğini analiz etmek için yöntemlere giriş

Ana konular: algoritmaların etkinliğinin deneysel ve analitik analizi.

N. Wirth'in klasik ifadesi "İyi bir program, iyi düşünülmüş bir algoritma ile etkili veri yapılarının birliğidir."

Algoritma Analizi
"Algoritma ve veri yapıları" kavramları bilgisayar teknolojisi alanının merkezinde yer alır, ancak belirli veri yapılarını ve algoritmaları "yüksek kaliteli ve verimli" olarak adlandırmak için bunları analiz etmeye yönelik hassas tekniklerin kullanılması gerekir. Doğal bir kalite kriteri olarak öncelikle yürütme süresinin ön plana çıkarılması doğaldır. Ayrıca, harcanan bellek ve disk alanı kaynaklarının miktarı, veri erişim hızı (veri yapısının verimliliği) de önemlidir. Kararların güvenilirliğine ve güvenilirliğine, istikrarına da dikkat edilmelidir.

Algoritma belirli bir uygulamaya bağlı olmamalıdır. Kullanılan programlama araçlarının çeşitliliği nedeniyle, uygulamada farklı olan algoritmalar, verimlilik açısından farklı sonuçlar üretebilmektedir.

Bir algoritmanın veya bir veri yapısı üzerindeki işlemin yürütme süresi, kural olarak bir dizi faktöre bağlıdır. Bir algoritmayı yürütmek için gereken süreyi belirlemenin en basit yolu, algoritmanın çalıştırılmasından önceki ve sonraki süreyi ölçmektir.

Ancak, bu zaman tahmin yönteminin doğru olmadığı unutulmamalıdır; her şeyden önce, modern işletim sistemlerinde birçok görevin paralel olarak yürütülebileceği ve bir test senaryosunun yürütülmesinin diğer türlerle birleştirilebileceği anlaşılmalıdır. aktivite. Ayrıca, istikrarlı bir bağımlılığın yalnızca tekrarlanan testler yapılarak elde edilebileceği anlaşılmalıdır, aksi takdirde, ilk verilerin özelliklerine ve diğer faktörlere bağlı olarak rastgele faktörlerin çalışmanın nihai sonucu üzerindeki etkisi nedeniyle, yürütme Algoritmanın zamanı da rastgele bir değişken olacaktır. Araştırma yaparken, algoritmayı farklı bir başlangıç ​​verileri kümesiyle çalıştırmak gerekir; genellikle verilerin kendisi rastgele oluşturulur, dolayısıyla farklı veri kümeleri nedeniyle harcanan zaman da farklı olacaktır.

Bir dizi tahmin elde edildikten sonra bir grafik oluşturulabilir ve tahmin edilebilir.

Böyle bir analiz, önemsiz olmayan algoritmalar kullanıldığında her zaman kullanılmalıdır; bu, hata ayıklama için birkaç düzine kayıt veya öğeden oluşan bir deneme kümesini değil, değişiklik yapılmasını veya hatta değiştirilmesini önleyen tam olarak gerçek verileri kullanan bir uygulama geliştirme önerisine benzer. Daha sonra pratik olmadıkları kanıtlanırsa, algoritma veya yapı verilerinin tamamen yeniden işlenmesi. Bir dizi deneysel sonuca sahip olarak, enterpolasyon ve ekstrapolasyon yapabilir ve algoritmanın gerçek koşullarda davranışını belirleyebilirsiniz.

Genel olarak, bir algoritmanın veya veri yapısı yönteminin yürütme süresinin, kaynak verinin boyutu arttıkça arttığını söyleyebiliriz, ancak bu aynı zamanda boyut eşit olsa bile veri türüne de bağlıdır. Ayrıca yürütme süresi, uygulamanın, derlemenin gerçekleştirildiği donanıma (işlemci, saat frekansı, bellek boyutu, disk alanı vb.) ve yazılıma (işletim ortamı, programlama dili, derleyici, yorumlayıcı vb.) bağlıdır ve algoritmanın yürütülmesi. Örneğin, diğer her şey eşit olduğunda, belirli miktarda kaynak veri için bir algoritmanın yürütme süresi, daha güçlü bir bilgisayar kullanıldığında veya algoritmayı makine kodunda bir program olarak yazarken, bir sanal makine tarafından yürütülmesine kıyasla daha az olacaktır. bunu bayt kodlarına dönüştürüyoruz.

Sonuç, algoritmaların ampirik analizini yürütmenin gerçekten güvenilir olmadığıdır. Ana dezavantajlar aşağıdaki üç noktaya indirgenebilir:

1) deneyler yalnızca sınırlı sayıda başlangıç ​​verisi kullanılarak gerçekleştirilebilir; Başka bir set kullanılarak elde edilen sonuçlar dikkate alınmaz.

2) iki algoritmanın etkinliğini karşılaştırmak için, bunların yürütme sürelerini belirlemeye yönelik deneylerin aynı donanım ve yazılım üzerinde yapılması gerekir;
3) Algoritmanın yürütme süresini deneysel olarak incelemek için uygulanmasını ve yürütülmesini gerçekleştirmek gerekir.

Böylece, algoritmaları analiz etmek için genel analiz yöntemlerini kullanma ihtiyacına geliyoruz; bu, aşağıdakilere olanak tanır:

1) çeşitli giriş verileri türlerini dikkate alır;

2) donanım ve yazılımdan bağımsız olarak herhangi iki algoritmanın göreceli etkinliğini değerlendirmenize olanak tanır;

3) algoritmanın açıklamasına göre, doğrudan uygulanmasına veya deneylerine gerek kalmadan gerçekleştirilebilir.

Genel analizin özü, f=f(n1, .., nm) fonksiyonunun belirli bir algoritmaya atanmasıdır. En basit haliyle, bir n1 değişkeninin (girdi verisi miktarının) bir fonksiyonudur. Ancak başka değişkenler de olabilir; örneğin hesaplamanın doğruluğu veya güvenilirliği. Bu nedenle, büyük sayılar durumunda (ikili gösterimin uzunluğu 200 bitten fazladır) belirli bir sayının asal olup olmadığını belirlemek için güvenilirliği değiştirilebilen olasılıksal bir yöntem kullanılır. En iyi bilinen fonksiyonlar doğrusal, kuvvet ve logaritmiktir. Bu nedenle onlarla çalışmanın temellerini hatırlamaya zaman ayırmalısınız.

Algoritmalar oluşturulurken ilk aşama bir programlama dili değil, insan dilindeki bir açıklama kullanılarak gerçekleşir. Bu tür açıklamalar program değildir ancak aynı zamanda sıradan metinlerden daha yapılandırılmıştır. Özellikle "üst düzey" açıklamalar, doğal dil ile ortak programlama dili yapılarını birleştirerek onları erişilebilir ve bilgilendirici hale getirir. Bu tür açıklamalar, veri yapısının veya algoritmanın üst düzey analizini kolaylaştırır. Bu tür açıklamalara genellikle sözde kod adı verilir. Ayrıca, sözde kodun analiz için belirli bir programlama dilindeki koddan daha yararlı olduğu da unutulmamalıdır.

Bazen belirli bir veri yapısına veya algoritmaya ilişkin belirli ifadelerin kanıtlanmasına ihtiyaç duyulur. Örneğin, algoritmanın doğruluğunu ve yürütme hızını göstermeniz gerekiyor. İfadeleri kesin olarak kanıtlamak için, ifadelerin kanıtı veya gerekçesi olarak hizmet edecek matematik dilini kullanmak gerekir. Bunu kanıtlamanın birkaç basit yolu vardır.

Bazen ifadeler genelleştirilmiş bir biçimde yazılır: “s kümesi v özelliğine sahip bir x elemanı içerir. Bu ifadeyi kanıtlamak için bu özelliğe sahip olan x'in s'ye ait olduğu örneğini vermek yeterlidir. Böyle genelleştirilmiş bir biçimde, kural olarak, olası olmayan ifadeler yazılır, örneğin: "S kümesinin her x öğesi P özelliğine sahiptir." Bu ifadenin yanlışlığını kanıtlamak için basitçe bir örnek vermek yeterlidir: x, P özelliğine sahip olmayan s'ye “aittir”. Bu durumda x elemanı bir karşı örnek görevi görecektir.

Örnek: n'nin 1'den büyük bir tam sayı olması durumunda 2^n - 1 formundaki herhangi bir sayının asal olduğu belirtilir. Bu ifade yanlıştır.

Kanıt: Birinin yanıldığını kanıtlamak için bir karşı örnek bulmanız gerekir.

Bu bir karşı örnektir: 2^4 - 1 = 15, 15= 3 * 5.

Çelişki yoluyla kanıta (olumsuzlamayı kullanarak) dayanan başka bir yol daha var. Bu durumda ana yöntemler çelişki ve çelişkidir. Karşıtlık yöntemlerinin kullanımı yansıtmaya benzer: "eğer x doğruysa, o zaman y doğrudur" ifadesini kanıtlamak için bunun tersini iddia edeceğiz: "eğer y yanlışsa, o zaman x yanlıştır." Mantıksal açıdan bakıldığında bu ifadeler aynıdır, ancak birincinin eş-biçimli hali olan ikinci ifade daha uygundur.

Örnek: a*b tek sayı ise a tektir veya b tektir.

Kanıt: Bu ifadeyi kanıtlamak için karşıtlığı düşünün: “Eğer a bir çift sayı ve b tek ise, o zaman a*b çifttir. Bazı x tam sayıları için a = 2*x olsun. O zaman a*b = 2*i*b olur ve bu nedenle a*b çarpımı çifttir.

Çelişki yoluyla ispat yöntemlerini kullanırken mantığı kullanmak faydalıdır.

A veya b = a veya b'nin veya hem a hem de b'nin aynı anda yürütülmesini gerektirir.
. a ve b = a ve b'nin aynı anda yürütülmesini gerektirir.
. a x veya b = a'nın yürütülmesini gerektirir, ancak b'yi gerektirmez veya b, ancak a'yı gerektirmez.

Bir q ifadesinin doğru olduğunu kanıtlamak için çelişki yöntemini kullanırken, önce q'nun yanlış olduğu varsayılır ve daha sonra böyle bir varsayımın bir çelişkiye yol açtığı gösterilir (örneğin, 2 * 2)<>4). Böyle bir çelişkiye vardığımızda, q'nun yanlış olduğu bir durumun mevcut olmadığını, dolayısıyla q'nun doğru olduğunu iddia edebiliriz.

Çoğu durumda, program yürütme zamanı veya alanıyla ilgili ifadeler, bir tamsayı parametresi n'yi (sorunun "boyutunu" temsil eden) kullanır. Daha sonra bir x(n) ifadesini formüle ettiğimizde, bir n değerleri kümesi için bu tür ifadeler eşdeğerdir. Bu ifade "sonsuz" bir sayı kümesi için geçerli olduğundan, kapsamlı bir doğrudan kanıt sağlamak imkansızdır. Bu gibi durumlarda tümevarım yöntemleri kullanılır. Tümevarım yöntemi şu gerçeğe dayanmaktadır; herhangi bir n > 1 için. Doğru olduğu bilinen bir şeyle başlayan ve sonuçta q(n)'nin doğru olduğuna dair bir kanıta ulaşan sonlu bir eylemler dizisi vardır. Dolayısıyla tümevarım yoluyla bir kanıt, q(n)'nin n=1,2,3 vb. için doğru olduğu ifadesiyle başlar. bir k sabitine kadar. Daha sonra, q(n+1), q(n+2) tümevarımlarının bir sonraki “adımının” n > k için de doğru olduğunu kanıtlıyoruz.

Algoritmalar analiz edilirken, işlem sayısı ve yürütme süresi hesaplanırken "küçük ayrıntılar" dikkate alınmamalı, sabit faktörler ve sabitler ihmal edilmelidir. Uygulamada büyük fonksiyon kavramı kullanılmaktadır. HAKKINDA. f(n) ve g(n) olmak üzere iki fonksiyonun olduğunu varsayalım, f(n) olduğu varsayılır.<= O(g(n)) , т.е. функция О ограничивает сверху значения функции f, начиная с n=n0.

Örneğin, bir dizideki sıfıra eşit öğe sayısını saymaya yönelik algoritma O(n) ile tanımlanır; burada n, öğe sayısıdır.

1) 20n3+7.2n2-21.78n + 5, O(n3) olarak tanımlanır

2)xn-2 + a(0), O(xn) olarak tanımlanır.

2) 3*log(n) + log(log(n)) O(log(n)) olarak tanımlanır.

3) 2100 O(1) olarak tanımlanır

4) 5/n, O(1/n) olarak tanımlanır.

Lütfen o(n) fonksiyonunun hedef zaman maliyet fonksiyonunu yukarıdan sınırladığını unutmayın, ancak her zaman maksimum doğruluk sağlayacak bir O(n) fonksiyonunu seçmeye çalışmalısınız.

Artan sırada en ünlü O fonksiyonları:

Asimptotik analizi kullanırken, O notasyonunu kullandığınızda genellikle sabit faktörleri ve toplama sabitlerini ihmal ettiğinize dikkat edin. Bununla birlikte, eğer bu değer yeterince büyükse, O(1) fonksiyonunun formu, O(n) fonksiyonu tarafından açıklanan algoritmaya göre daha fazla tercih edilse de, elbette pratik uygulama kazanacak olan ikinci algoritma olacaktır.

f(n) fonksiyonunun tipine bağlı olarak, aşağıdaki algoritma karmaşıklık sınıfları ayırt edilir.

Karmaşıklık fonksiyonuna bağlı olarak algoritma karmaşıklık sınıfları
f(n)'yi görüntüle	Algoritma sınıfının özellikleri
	Çoğu işleve ilişkin talimatların çoğu bir veya daha fazla kez yürütülür. Bir programdaki tüm komutlar bu özelliğe sahipse programın yürütme süresi sabittir.
günlük N	Bir programın yürütme süresi logaritmik olduğunda, N arttıkça program yavaşlar.Bu tür yürütme süreleri tipik olarak büyük bir sorunu bir dizi daha küçük alt soruna indirgeyen, sorunun boyutunu her adımda sabit bir faktörle azaltan programlarla ilişkilidir. Tabanın değiştirilmesi logaritmanın değerindeki değişimi büyük ölçüde etkilemez: n
N	Bir programın yürütme süresi doğrusal olduğunda, bu genellikle her giriş öğesinin çok az işlemden geçtiği anlamına gelir.
N günlük N	N log N ile orantılı çalışma zamanı, bir algoritmanın bir sorunu daha küçük alt problemlere bölerek, bunları bağımsız olarak çözerek ve ardından çözümleri birleştirerek çözdüğü zaman ortaya çıkar.
N 2	Bir algoritmanın çalışma süresi ikinci dereceden olduğunda, nispeten küçük problemlerin çözümünde pratik kullanım için kullanışlıdır. İkinci dereceden yürütme süresi tipik olarak tüm veri öğesi çiftlerini (belki de çift yuvalama döngüsünde) işleyen algoritmalarda görünür.
N 3	Veri öğelerinin üçlüsünü (muhtemelen üçlü yuvalama döngüsünde) işleyen benzer bir algoritmanın kübik yürütme süresi vardır ve pratik olarak yalnızca küçük problemler için uygulanabilir.
2N	Üstel çalışma süresine sahip yalnızca birkaç algoritmanın pratik uygulamaları vardır, ancak bu tür algoritmalar, kaba kuvvet gibi bir sorunu doğrudan çözmeye çalışırken doğal olarak ortaya çıkar.

Sonsuzdaki karmaşıklığın asimptotik fonksiyonlarını incelemek için matematiksel yöntemlere dayanarak, beş algoritma sınıfı tanımlanır.

1. Sabit yürütme süresine sahip hızlı algoritmaların bir sınıfı, karmaşıklık fonksiyonu O(1)'dir. Ara durum, yine bu sınıfta sınıflandırılan O(log N) karmaşıklığına sahip algoritmalar tarafından işgal edilir.

2. Karmaşıklık fonksiyonu giriş parametrelerinden polinom olarak belirlenen bir rasyonel veya polinom algoritmaları sınıfı. Örneğin, O(N), O(N 2, O(N 3).

3. Karmaşıklık derecesi O(N log N) olan bir alt-üstel algoritmalar sınıfı.

4.O(2 N) karmaşıklık derecesine sahip üstel algoritmalar sınıfı.

5.Aşırı üstel algoritmaların sınıfı. Faktöriyel karmaşıklığa sahip algoritmalar vardır, ancak bunların genellikle pratik bir uygulaması yoktur.

Algoritmanın yürütülmesi sırasındaki hafıza durumu, belirli alanların tahsis edilmesini gerektiren değerler tarafından belirlenir. Bu durumda problemin çözümü sırasında ilave sayıda hücre kullanılabilir. A algoritmasının D girişi için ihtiyaç duyduğu bellek miktarıyla, algoritmanın yürütülmesi sırasında kullanılan maksimum bellek hücresi sayısını kastediyoruz. Bir algoritmanın kapasite karmaşıklığı, algoritmanın en kötü durum bellek kapasitesi fonksiyonunun asimptotik tahmini olarak tanımlanır.

Bu nedenle, bir algoritmanın en kötü, ortalama ve en iyi durumlardaki kaynak karmaşıklığı, asimptotik gösterimle belirlenen ve söz konusu duruma karşılık gelen, zaman ve kapasite karmaşıklığının sıralı bir fonksiyon sınıfı çifti olarak tanımlanır.

Prosedürel programlamadaki ana algoritmik yapılar takip, dallanma ve döngüdür. Sabit bir girdi boyutuyla en iyi, ortalama ve en kötü durumlar için karmaşıklık fonksiyonlarını elde etmek için, ana algoritmik yapıların değerlendirilmesindeki farklılıkların dikkate alınması gerekir.

• “Aşağıdaki” yapının karmaşıklığı birbirini takip eden blokların karmaşıklığının toplamıdır: f=f 1 +f 2 +...+f n .
• "Dallanma" tasarımının karmaşıklığı, koşul tarafından belirlenen talimatların her birine geçiş olasılığı ile belirlenir. Aynı zamanda durumun kontrol edilmesi de belli bir karmaşıklığa sahiptir. En kötü durumun karmaşıklığını hesaplamak için en fazla karmaşıklığa sahip olan dallanma bloğu seçilebilir; en iyi durum için ise daha az karmaşıklığa sahip olan blok seçilebilir. f if =f 1 +f sonra p sonra +f else (1-p o zaman)
• "Döngü" yapısının karmaşıklığı, döngü sonlandırma koşulunun (genellikle 0(1) düzeyinde) ve döngü gövdesinin mümkün olan en büyük operasyon sayısına göre döngünün tamamlanan yineleme sayısının çarpımının hesaplanmasıyla belirlenir. İç içe döngüler kullanılırsa karmaşıklıkları artar.

Böylece, bir algoritmanın karmaşıklığını tahmin etmek için karmaşıklık fonksiyonunu elde etmeye yönelik genel bir yöntem formüle edilebilir.

1. Algoritmanın ayrıştırılması, algoritmadaki temel yapıların tanımlanmasını ve karmaşıklığın tahmin edilmesini içerir. Bu durumda ana algoritmik yapılardan aşağıdakiler dikkate alınır.
2. Temel dil işlemleri için emek yoğunluğunun satır satır analizi, ya kümülatif bir analizi (tüm işlemleri hesaba katarak) ya da operasyonel analizi (her işlemin karmaşıklığını hesaba katarak) gerektirir.
3. En iyi, ortalama ve en kötü durumlar için temel algoritmik yapıların analiz edilmesine yönelik metodolojiye dayalı karmaşıklık fonksiyonunun ters bileşimi.

Özyinelemeli algoritmaların kaynak verimliliğini değerlendirmenin bir özelliği, ek bellek maliyetlerini ve özyinelemeyi organize etme mekanizmasını hesaba katma ihtiyacıdır. Bu nedenle, algoritmaların özyinelemeli uygulamalarının karmaşıklığı, bir özyinelemeli çağrı sırasında gerçekleştirilen işlemlerin yanı sıra bu tür çağrıların sayısıyla da ilgilidir. Değerlerin iadesi ve kontrolün çağrı noktasına aktarılmasının maliyetleri de dikkate alınır. Gerekli yığın belleğini tahmin ederken, belirli bir zamanda yığında depolananın bir özyineleme parçası değil, yinelemeli çağrılar zinciri olduğunu dikkate almanız gerekir. Bu nedenle yığın boyutu, alınan eş zamanlı özyinelemeli çağrıların mümkün olan maksimum sayısına göre belirlenir.

Programcının kütüphanesi

“Hata ayıklama, hataları ortadan kaldırma süreciyse, programlama da onları tanıtma süreci olmalıdır”

E. Dijkstra

1.2. Neden algoritmaları incelemelisiniz? Algoritmaların verimliliği

İlk olarak, algoritmalar bilgisayar biliminin çeşitli alanlarındaki herhangi bir problemi çözmek için hayati bileşenlerdir. Algoritmalar, teknoloji gelişiminin mevcut aşamasında önemli bir rol oynamaktadır. Burada aşağıdaki gibi ortak görevleri hatırlayabilirsiniz:

• değişen karmaşıklıktaki matematiksel denklemlerin çözümü, matrislerin çarpımının bulunması, ters matrisler;
• malları ve insanları taşımanın en uygun yollarını bulmak;
• Kaynakları çeşitli düğümler (üreticiler, makineler, işçiler, işlemciler vb.) arasında dağıtmak için en uygun seçenekleri bulmak;
• genomda eşleşen dizilerin bulunması;
• küresel internette bilgi aramak;
• e-ticarette finansal kararlar almak;
• ses ve video bilgilerinin işlenmesi ve analizi.

Bu liste uzar gider ve aslında bilgisayar bilimi ve bilişim biliminde belirli algoritmaların kullanılmadığı bir alan bulmak neredeyse imkansızdır.

İkinci olarak, yüksek kaliteli ve verimli algoritmalar, ilk bakışta bilgisayar bilimlerinden (kuantum mekaniği, ekonomi ve finans, evrim teorisi) uzak olan sektörlerde atılımların katalizörü olabilir.

Üçüncüsü, algoritma çalışmak aynı zamanda matematiksel yeteneklerimizi ve mantıksal düşüncemizi geliştiren inanılmaz derecede ilginç bir süreçtir.

1.3. Algoritmaların verimliliği

Bir bilgisayarın hızının ve bellek miktarının sonsuza kadar artırılabileceğini varsayalım. O zaman algoritmaları incelemeye gerek olur mu? Evet, ancak yalnızca ayrıştırma yönteminin sınırlı bir çalışma süresine sahip olduğunu ve doğru cevabı verdiğini göstermek için. Bilgisayarlar sonsuz hızlı olsaydı, bir sorunu çözmek için keyfi olarak doğru bir yöntem işe yarardı. Tabii ki, çoğu zaman uygulaması daha kolay olan yöntem seçilecektir.

Günümüzde bilgisayarlar çok güçlü ama hızları sonsuz değil, hafızaları da öyle. Dolayısıyla matematikte, gereken hafıza miktarı kadar sınırlı bir kaynaktır. Bu kaynakların akıllıca kullanılması, zaman ve hafıza kaynaklarının kullanımı açısından verimli algoritmaların kullanılmasıyla kolaylaştırılmıştır.

Aynı sorunu çözmek için tasarlanan algoritmaların verimliliği genellikle büyük farklılıklar gösterebilir. Bu farklılıklar, farklı donanım ve yazılımlardan kaynaklanan farklılıklardan çok daha belirgin olabilir.

Yukarıda belirtildiği gibi, bu bölüm sıralama görevine odaklanacaktır. Dikkate alınacak ilk algoritma, dahil etme sıralaması, çalışması için zaman gerektirir; bunun miktarı c 1 n 2 olarak tahmin edilir; burada n, girdi verilerinin boyutudur (sıralanacak dizideki öğelerin sayısı), c 1 bir sabittir. Bu ifade, algoritmanın çalışma süresinin kaynak verinin hacmine nasıl bağlı olduğunu gösterir. Dahil etme sıralaması durumunda bu bağımlılık ikinci derecedendir. İkinci algoritma olan birleştirme sıralaması, miktarı 2 nLog 2 n olarak tahmin edilen zaman gerektirir. Tipik olarak dahil etme sıralama sabiti, birleştirme sıralama sabitinden daha küçüktür; yani, n arttıkça c12, ILog 2 n işlevinden daha hızlı büyür. Ve bir n = n 0 değeri için, sabitlerdeki farkın etkisinin önemi sona erdiğinde bir ana ulaşılacaktır ve gelecekte herhangi bir n > n 0 için c 2 nLog 2 n fonksiyonu c 1 n 2'den küçük olacaktır.

Bunu göstermek için iki bilgisayarı düşünün: A ve B. A bilgisayarı daha hızlıdır ve sıralama algoritmasını çalıştırır; B bilgisayarı ise daha yavaştır ve birleştirme sıralama algoritmasını çalıştırır. Her iki bilgisayar da bir milyon sayıdan oluşan bir kümeyi sıralamalıdır. Diyelim ki A bilgisayarı saniyede bir milyar işlem gerçekleştiriyor ve B bilgisayarı yalnızca on milyon işlem yapıyor, A bilgisayarı B'den 100 kat daha hızlı çalışıyor. Farkı daha belirgin hale getirmek için etkinleştirme yönteminin kodunun en iyi kişi tarafından yazıldığını varsayalım. Dünyadaki programcının işlemciye talimatlar vermesi ve bu algoritmayla n sayıda sayıyı sıralaması için 2n 2 işlem (yani C 1 = 2) gerçekleştirmesi gerekir. B bilgisayarındaki birleştirme sıralaması, acemi bir programcı tarafından yüksek seviyeli bir dil kullanılarak yazılmıştır ve ortaya çıkan kod, 50nlog 2 n işlem gerektirir (yani, c 2 = 50). Dolayısıyla bir milyon sayıyı sıralamak için A bilgisayarının

ve B bilgisayarına -

Bu nedenle, kötü bir bilgisayar ve kötü bir derleyiciyle bile çalışma süresi daha yavaş artan kodu kullanmak, çok daha az CPU zamanı gerektirir! 10.000.000 basamağın sıralanması için, birleştirme sıralamasının avantajı daha da belirgin hale gelir: dahil etme sıralaması böyle bir görev için yaklaşık 2,3 gün gerektirirken, birleştirme sıralaması için bu süre 20 dakikadan az sürer. Genel kural, sıralanacak öğe sayısı arttıkça birleştirme sıralamasının avantajının da artacağıdır. Yukarıdaki örnek, bilgisayar yazılımı gibi algoritmaların da olduğunu göstermektedir. teknoloji. Genel sistem performansı, donanımın gücüne olduğu kadar algoritmanın verimliliğine de bağlıdır.

Bu nedenle, en basit Turing makinelerinden homojen bir bilgi işlem ortamına kadar bilgi işlem makineleri için çeşitli seçenekler göz önünde bulundurulur. Hepsi bir algoritmanın mevcut olduğu sorunları çözmek için kullanılabilir. Bu modellere dayanarak, daha özel hesaplama modelleri oluşturulmuştur: dallanmayan aritmetik programlar, bit düzeyinde hesaplama, ikili vektör hesaplama ve karar ağaçları.

Algoritmalar aşağıdaki özelliklere sahiptir:

a) karmaşıklık;

b) emek yoğunluğu;

c) güvenilirlik vb.

Algoritmaların karmaşıklığını değerlendirmek için birçok kriter vardır. Çoğu zaman ilgileneceğiz büyüme sırası Giriş verisi miktarı arttıkça sorunu çözmek için gereken zaman ve hafıza kapasitesi artar. Her özel göreve, onun adı verilen belirli bir sayıyı ilişkilendirelim. boyut. Örneğin, bir matris çarpım probleminin boyutu, faktör matrislerinin en büyük boyutu olabilir; Bir grafikteki problemin boyutu, belirli bir grafiğin kenar sayısı vb. olabilir.

Bir algoritmanın problem boyutunun bir fonksiyonu olarak harcadığı zamana denir. zaman karmaşıklığı bu algoritma. Problem boyutu arttıkça bu karmaşıklığın limitteki davranışına denir. asimptotik zaman karmaşıklığı. Benzer şekilde tanımlanmış kapasitif karmaşıklık Ve asimptotik kapasite karmaşıklığı.

Biçimsel hesaplamalı modelleri dikkate almanın önemli bir motivasyonu, hesaplama süresi için alt sınırlar elde etmek amacıyla çeşitli problemlerin hesaplama karmaşıklığını ortaya çıkarma arzusudur. Belirli bir görevi belirli bir süreden daha kısa sürede tamamlayabilecek hiçbir algoritmanın olmadığını göstermek, bir algoritmanın ne olduğuna ilişkin kesin ve bazen oldukça uzmanlaşmış bir tanım gerektirir. Böyle bir tanımın bir örneği Turing makineleridir.

4.1.1. Çerçeve ve çerçeve makineleri*

İki araba düşünün:

1. Belleğe rastgele erişime sahip makineler (eşit erişim adresli makine - RAM), program talimatlarının kendilerini değiştiremediği tek toplayıcılı bir bilgisayarı modeller.

2. Saklanan program modeli, belleğe rastgele erişime sahip ve talimatları (RAM*) değiştirme yeteneği olan bir makinedir.

Şekil 2.9 RAM makinelerinin yapısı (RAM*)

RAM için program belleğe yazılmaz, dolayısıyla program kendini değiştirmez. Bir program, etiketlenmiş komutların bir dizisidir. Aritmetik talimatlar, G/Ç talimatları, dolaylı adresleme talimatları ve dallanma talimatları vardır. Tüm hesaplamalar, diğer herhangi bir bellek kaydı gibi isteğe bağlı bir tamsayı saklayabilen r 0 (toplayıcı) kaydında gerçekleştirilir. Her komut iki bölümden oluşur; bir işlem kodu ve bir adres. PAM komutları, Assembly dili komutlarının bir alt kümesidir; bu alt küme isteğe göre genişletilebilir ancak görevlerin karmaşıklık sırası değişmeyecektir.

İşlenen aşağıdaki türlerden biri olabilir:

1. =ben tam sayının kendisi anlamına gelir Ben ve değişmez olarak adlandırılır;

2. Ben- içerikleri kaydedin Ben (Ben negatif olmamalıdır);

3. *Ben dolaylı adresleme anlamına gelir, yani işlenenin değeri yazmacın içeriğidir J,Nerede J- kayıt defterindeki bir tam sayı BEN;Eğer J<0, araba durur.

Programın değerini belirleyebilirsiniz R iki nesne kullanır: negatif olmayan bir tamsayılar kümesinden bir tamsayılar kümesine c eşlemesi ve yürütülecek bir sonraki komutu belirleyen bir "komut sayacı". c fonksiyonu hafıza ekranı, yani c(i)- kayıt numarasında bulunan tamsayı BEN (içerik kayıt olmak BEN).

Başlangıçta с(i)=0 hepsi için Ben 0 , program sayacı P'deki ilk talimata ayarlanmıştır ve çıkış bandı boştur. İnfazdan sonra k gelen takım R sayaç otomatik olarak şuna geçer: (k+1)-th (yani bir sonrakine) komutu, eğer k-benim takımım JUMP, HALT, JGTZ ve benzeri bir takım değildi.

RAM* programı hafıza kayıtlarında bulunur. Her RAM* komutu ardışık iki hafıza kaydını kaplar: ilk kayıt işlem kodunu, ikincisi ise adresi içerir. RAM* talimatları seti, dolaylı adresleme dışında her şeyde RAM için karşılık gelen setle örtüşür; bu hariçtir: RAM*, programın yürütülmesi sırasında talimatları değiştirerek dolaylı adreslemeyi simüle edebilir.

Öğrencinin çözüm olarak uyguladığı algoritmanın belirli başlangıç ​​verileri verildiğinde probleme doğru cevabı üretip üretemediğinin kontrol edilmesinin yanı sıra, çözüm kontrol edilirken programın çalışma süresi de dikkate alınır. Bu, istisnasız tüm görevler için en uygun algoritmaları yazmanın hayati derecede önemli olduğu anlamına gelmez (bu, bunların yetkin bir şekilde uygulanması ve hata ayıklaması genellikle çok zaman alabilir). Bu basitçe bazı bireysel görevlerde zaman parametresinin çok önemli bir rol oynayabileceği anlamına gelir. Bazı Olimpiyat turlarında optimalliğin gerekli olduğu tek bir sorun bile olmayabilir. Ancak bunun tersi de gerçekleşebilir.

Bu nedenle hem öğrenciler hem de öğretmenler farklı algoritmaları etkililiklerine göre karşılaştırabilmelidir. Okul çocukları - bir sorunu doğru zamanda çözmenin en uygun yolunu seçmek için, öğretmenler - görevleri yetkin bir şekilde seçmeli ve belirli bir sorunun yazarının tam olarak bu tür zaman sınırlarını belirlerken aklında hangi çözümü düşündüğünü anlamalıdır.

Algoritmanın etkinliğini değerlendirmek için O olarak gösterilen bir karmaşıklık fonksiyonu kullanılır (“yaklaşık büyük” olarak okunur). Aslında başka değerlendirmeler de var, ancak öğrencinin çeşitli algoritmalarla yeni tanışmaya başladığı aşamada bunlara gerçekten ihtiyaç duyulmuyor. Karmaşıklık işlevi, kaynak verilere veya bunların miktarına bağlı olarak program yürütme süresinin artacağı modeli yansıtır.

Yürütme süresi başlangıç ​​verilerine bağlı olan bir algoritma örneği, N sayısının tüm doğal bölenlerini bulmaya yönelik algoritmadır. Açıkçası, sayı ne kadar büyükse, gerçekleştirilmesi gereken döngü adımları da o kadar fazla olacaktır. Yürütme süresi girdi verilerinin miktarına bağlı olan bir algoritma örneği, bir dizideki en büyük sayıyı aramak olabilir. Dizi ne kadar uzun olursa hangi sayının en büyük olduğunu belirlemek için o kadar fazla karşılaştırma işlemi yapılması gerekir.

Ana işlevler şunlardır:

lO(1) - böyle bir karmaşıklık fonksiyonu, programın çalışma süresinin herhangi bir başlangıç ​​verisi için sabit olduğunu gösterir;

l O(N) - işlem sayısı N ile orantılı olarak artar (burada N, bir görev parametresi veya dizideki öğelerin sayısı olabilir).

l O(log N) - işlem sayısı N'nin logaritmasıyla orantılı olarak artar (bu tam olarak, örneğin sıralı bir dizide bir öğe ararken yarıya yönteminin karmaşıklığıdır). N büyüklük sırasına göre arttıkça işlem sayısı bir değişir. Logaritmanın tabanı genellikle belirtilmez; biz büyümenin doğasıyla (hızlı/yavaş) ilgileniyoruz, zamanın kesin değeriyle değil.

l O(N2) - N'nin karesi ile orantılı olarak işlem sayısı artar. Genel olarak problemin karmaşıklığına bağlı olarak O(Nk) olabilir.

l O(N!) - işlem sayısı faktöriyel N ile orantılı olarak artar.

Tüm işlemlerin aynı sürede gerçekleştirilmemesi nedeniyle burada bir takım incelikler vardır, bu nedenle zaman karmaşıklığı tahmin edilirken en fazla zaman gerektiren işlemler kullanılır.

Çoğu zaman, algoritmaları tanımlarken, çalışma sürelerine ilişkin bir tahmin, giriş/çıkış işlemlerini hesaba katmadan saf haliyle verilir.

Örnek: Klavyeden bir diziye giren ve içindeki en büyük elemanı bulan bir programın karmaşıklığını tahmin edelim.

İşlem sayısını N+(N-1)+1=2N olarak toplayalım. Yani öyle bir sabit vardır ki herhangi bir N için işlem sayısı CN'yi aşmaz. Bu nedenle algoritmanın karmaşıklığı O(N)'dir.

Örnek: Klavyeden bir diziye giren ve içinde belirli bir özelliğe sahip (örneğin, belirli bir değere eşit) bir öğe bulan bir programın karmaşıklığını tahmin edelim.

Algoritma aşağıdaki adımlardan oluşur:

Belirli bir özelliğe sahip bir öğeyi arayarak bir dizi girme (N giriş işlemi) (ne kadar şanslı: öğe dizinin başına daha yakın veya en sonuna yerleştirilebilir; öğe mevcut değilse o zaman şunu yapmanız gerekir: bundan emin olmak için tüm N karşılaştırmaları yapın) sonucun çıktısı.

En iyi durumda, bu algoritma N+2 işlem (tüm dizinin girişi, tek bir karşılaştırma, çıkış), en kötü durumda (böyle bir öğe olmadığında - 2N+1 işlem) gerektirecektir. Eğer N büyük bir sayı ise, örneğin yaklaşık 106 ise, o zaman birlik ihmal edilebilir. Bu nedenle algoritmanın karmaşıklığı O(N)'dir.

Örnek: L uzunluğundaki bir kelime şifreleme algoritmasının karmaşıklık fonksiyonunu ikame yöntemini kullanarak belirleyelim. Alfabenin her karakteri için değiştirilmesi gereken karakterin yazıldığı bir tablo olsun. S alfabesindeki harf sayısını gösterelim.

Algoritma aşağıdaki adımlardan oluşur:

Tüm karakterler arasında bir sözcük girme (tek işlem) döngüsü

1. her karakter için, tabloda yerini bulun (tablo sıralı değilse ve aramayı kolaylaştıracak herhangi bir özelliğe sahip değilse, en kötü durumda, aranan öğe en alttaysa bir karakter için S işlemi vardır) son)

2. bulunan sembolün çıktısı

Döngünün sonu

Toplam işlem sayısı 1+(S+1)*L'dir. Yeterince büyük S ve L birimlerinin ihmal edilebilmesi durumunda, bu algoritmanın karmaşıklık fonksiyonunun O(S*L) olduğu ortaya çıkar.

Örnek: N doğal sayısını ikili sayı sistemine (veri giriş ve çıkış işlemleri olmadan) dönüştürmek için algoritmanın karmaşıklık fonksiyonunu tanımlayalım.

Algoritma aşağıdaki adımlardan oluşur:

Bir sayıyı 2'ye bölmenin sonucu 0 olana kadar döngü

1. Sayıyı 2'ye bölün ve kalanı hatırlayın

2. bölme sonucunu yeni bir sayı olarak alın

Döngünün sonu

Toplam işlem sayısı 1+log2N'yi geçmez. Dolayısıyla bu algoritmanın karmaşıklığı O(log N)'dir.

Bir program farklı karmaşıklık fonksiyonlarına sahip birkaç bölümden oluşuyorsa, o zaman Ö Daha büyük karmaşıklık fonksiyonu, daha küçük olanları “emecektir”. Örneğin, sıralı dizinin O(N) dizi girişini, O(N2) sıralamasını ve O(N) çıkışını yaparsanız, programın tamamının O(N2) karmaşıklığına sahip olduğunu söyleyebilirsiniz.

Algoritmaların karmaşıklık fonksiyonları hakkındaki bilginin pratik uygulaması iki yönlüdür. Öncelikle belirli bir görev için literatürde konuyla ilgili veriler varsa daha optimal bir algoritma seçilebilir. İkinci olarak, bir öğrenci başlangıç ​​verilerinin bir seti üzerinde kendi çözümünün çalışma süresini bilerek, belirli bir problem için maksimum kısıtlamalara karşılık gelen veriler üzerinde aynı programın çalışma süresini yaklaşık olarak tahmin edebilir.

Sorular

Bu görevler sunulan materyal üzerinde kendi kendini test etmek için kullanılır ve zorunlu değildir.

1. İkinci dereceden bir denklemin çözümü için algoritmanın karmaşıklık fonksiyonunu belirleyin.

2. Belirli bir kenar sayısına dayalı olarak düzenli bir çokgen çizmeye yönelik algoritmanın karmaşıklık fonksiyonunu belirleyin.

3. Belirli bir konumdaki bir diziye bir öğe eklemek için algoritmanın karmaşıklık fonksiyonunu belirleyin (belirli sayıdan büyük veya ona eşit sayılara sahip tüm öğelerin birer birer sağa ön kaydırılmasıyla).

4. Bir sütuna iki doğal sayı eklemek için kullanılan algoritmanın karmaşıklık fonksiyonunu belirleyin (A, ilk sayının basamak sayısı, B ikincinin basamak sayısı olsun).

5. Bir sütundaki iki doğal sayının çarpımı için algoritmanın karmaşıklık fonksiyonunu belirleyin.