Algoritmanın zaman karmaşıklığının tahmini. Algoritma karmaşıklığı fonksiyonlarının türleri

sabit zaman

Bir algoritmanın bir algoritma olduğu söylenir. sabit zaman(zaman olarak kaydedildi O(1)) eğer değer T(n) girdinin boyutundan bağımsız bir değerle sınırlıdır. Örneğin, bir dizide bir eleman almak sabit zaman alır çünkü onu bulmak için tek bir komut yürütülür. Ancak, sıralanmamış bir dizide minimum değeri bulmak, dizinin her bir elemanına bakmamız gerektiğinden sabit zamanlı bir işlem değildir. Böylece, bu işlem lineer zaman alır, O(n). Eleman sayısı önceden biliniyorsa ve değişmiyorsa böyle bir algoritma sabit zamanlı algoritma olarak adlandırılabilir.

"Sabit zaman" ismine rağmen, çalışma süresi görevin boyutundan bağımsız olmak zorunda değildir, ancak çalışma süresindeki üst sınır olmamalıdır. Örneğin, "değişim değerleri" görevi a ve B, gerekirse, sonuç için a≤B", sabit bir zaman problemi olarak kabul edilir, ancak algoritmanın çalışma süresi eşitsizliğin olup olmamasına bağlı olabilir. a ≤ B ya da değil. Ancak, bir sabit var T, bunun için görev yürütme süresi her zaman aşmaz T.

Sabit zamanda çalışan bazı kod örnekleri aşağıdadır:

int dizin = 5; int öğe = liste; Eğer(koşul doğru) sonraBaşka sabit çalışma süresi ile bazı işlemleri gerçekleştirin için ben = 1 ile 100 için j = 1 ile 200, sabit çalışma süresi ile bazı işlemleri gerçekleştirir

Eğer T(n) eşittir O( bazı sabit değer), eşdeğerdir T(n) O(1)'dir.

logaritmik zaman

logaritmik zaman, Eğer T(n) = O(günlük n) . Bilgisayarlar ikili sayı sistemini kullandığından, logaritmanın temeli olarak 2 kullanılır (yani, log 2 n). Ancak, ne zaman baz değiştirme logaritmalar log a n ve günlük b n sadece O-büyük gösterimde atılan sabit bir faktör ile farklılık gösterir. Yani O(günlük n) logaritmanın tabanından bağımsız olarak logaritmik zaman algoritmaları için standart gösterimdir.

Logaritmik zamanda çalışan algoritmalar, ikili ağaçlar üzerindeki işlemlerde veya ikili aramalar kullanılırken yaygın olarak karşılaşılır.

O(log n) algoritmaları, eleman sayısı arttıkça eleman başına yürütme süresi azaldığından oldukça verimli olarak kabul edilir.

Böyle bir algoritmanın çok basit bir örneği, bir dizgiyi ikiye bölmek, ardından diğer yarısını tekrar ikiye bölmek vb. olabilir. Bu, O(log n) zaman alır (burada n, dizenin uzunluğudur, burada varsayıyoruz ki konsol günlüğü ve str.alt dize sabit zaman ayırın). Bu, mühür sayısını artırmak için hattın uzunluğunu iki katına çıkarmanız gerektiği anlamına gelir.

// Bir dizgenin sağ yarısını yinelemeli olarak yazdırma işlevi var sağ = işlev (dizi) (var uzunluk = dizge.uzunluk; // yardımcı fonksiyon var help = function(index)( // Özyineleme: sağ yarıyı yazdır if (dizin< length ) { // Dizinden satır sonuna kadar karakterleri yazdır konsol. log (str .substring (index , length )); // özyinelemeli çağrı: sağ tarafla yardımcı işlevi çağırın help (Matematik .ceil ((uzunluk + indeks ) / 2 )); ) yardım(0); )

polilogaritmik zaman

Algoritmanın çalıştığı söyleniyor polilogaritmik zaman, Eğer T(n) = O((günlük n) k), bazı k. Örneğin, matris çarpımının sırası ile ilgili problem polilogaritmik zamanda şu şekilde çözülebilir: paralel RAM makinesi .

çizgi altı zaman

Algoritmanın çalıştığı söyleniyor çizgi altı zaman, Eğer T(n) = o( n). Özellikle, yukarıda listelenen zaman karmaşıklığı algoritmalarının yanı sıra Grover's O( n ½).

Kesin olmakla birlikte, yine de alt çizgisel zamanda çalışan, süreç paralelleştirmesini (NC 1 matris determinant hesaplamalarında olduğu gibi), klasik olmayan hesaplamaları (Glover'ın aramasında olduğu gibi) kullanan veya girdi yapısı üzerinde garantili bir tahmine sahip olan (olduğu gibi) tipik algoritmalar. logaritmik zamanda çalışanlar, ikili arama algoritmaları ve birçok ağaç işleme algoritması). Bununla birlikte, dizinin ilk log(n) bitleri tarafından belirlenen konumda bit 1'e sahip tüm diziler kümesi gibi biçimsel yapılar, girdinin her bir bitine bağlı olabilir, ancak yine de zaman içinde alt çizgide kalır.

Terim alt doğrusal çalışma süresi ile algoritma genellikle, yukarıdaki örneklerden farklı olarak, geleneksel sıralı makine modellerinde çalışan ve giriş yapısı hakkında ön bilgi gerektirmeyen algoritmalar için kullanılır. Bununla birlikte, olasılık yöntemlerini kullanmalarına izin verilir ve dahası, algoritmaların çoğu önemsiz problem için olasılıklı olması gerekir.

Böyle bir algoritma, girdiyi tam olarak okumadan bir yanıt vermesi gerektiğinden, girdi akışında izin verilen erişim yöntemlerine büyük ölçüde bağımlıdır. Tipik olarak bir bit dizisi olan bir akış için B 1 ,...,bk, algoritmanın değeri O(1) zamanında talep edebileceği varsayılır. ben herkes için Bence.

Alt çizgisel zaman algoritmaları genellikle olasılıklıdır ve yalnızca yaklaşık bir çözüm verir. Alt doğrusal çalışma zamanı algoritmaları, çalışmada doğal olarak ortaya çıkar mülk kontrolleri.

Doğrusal zaman

doğrusal zaman, veya Ö( n) , eğer karmaşıklığı O( n). Gayri resmi olarak bu, yeterince büyük bir girdi boyutu için çalışma süresinin girdi boyutuyla doğrusal olarak arttığı anlamına gelir. Örneğin, bir listenin tüm öğelerini toplayan bir prosedür, listenin uzunluğuyla orantılı olarak zaman alır. Çalışma süresi, özellikle küçük değerler için, kesin orantılılıktan önemli ölçüde farklı olabileceğinden, bu açıklama tamamen doğru değildir. n.

Doğrusal zaman genellikle bir algoritmanın istenen bir özelliği olarak görülür. (Neredeyse) doğrusal çalışma süresine veya daha iyisine sahip algoritmalar oluşturmak için pek çok araştırma yapılmıştır. Bu çalışmalar hem yazılım hem de donanım yaklaşımlarını içermektedir. Donanım yürütmesi durumunda, matematiksel bir bakış açısından, standart hesaplama modellerinde asla doğrusal yürütme süresine ulaşamayan bazı algoritmalar, doğrusal zamanda çalışabilir. Bu amaca ulaşmak için paralelliği kullanan bazı donanım teknolojileri vardır. İlişkisel bellek buna bir örnektir. Bu doğrusal zaman kavramı, Boyer-Moore algoritması ve Ukkonen algoritması gibi dizi karşılaştırma algoritmalarında kullanılır.

yarı-doğrusal zaman

Bir algoritmanın, aşağıdaki durumlarda yarı-doğrusal zamanda çalıştığı söylenir: T(n) = Ö( n kayıt k n) bazı sabitler için k. Doğrusal-logaritmik zaman ile özel bir durumdur k= 1. Zayıf-O gösterimini kullanan bu algoritmalar q( n). Quasilineer zaman algoritmaları da o( n 1+ε) herhangi bir ε > 0 için ve herhangi bir polinomdan daha hızlı çalışır. n

Yukarıda bahsedilen lineer logaritmik algoritmalara ek olarak, yarı lineer zamanda çalışan algoritmalar şunları içerir:

Sıralamayı yerinde birleştir , O( n kayıt 2 n)
Hızlı Sıralama , O( n kayıt n), olasılıksal versiyonda, en kötü durum lineer logaritmik yürütme süresine sahiptir. Olasılıksız sürüm, yalnızca karmaşıklığı ortalama olarak ölçmek için doğrusal-logaritmik bir çalışma süresine sahiptir.
Yığın Sıralaması , O( n kayıt n), birleştirme sıralama , introsort , ağaç destekli ikili sıralama, düzgün sıralama , solitaire sıralama, vb. en kötü ihtimalle
Fast Fourier dönüşümleri , O( n kayıt n)
Monge matrislerinin hesaplanması , O( n kayıt n)

Doğrusal-logaritmik zaman

Doğrusal-logaritmik, üslü yarı doğrusal zamanın özel bir durumudur. k= 1 logaritmik terimde.

Doğrusal-logaritmik fonksiyon formun bir fonksiyonudur n kayıt n(yani ürün doğrusal ve logaritmik terimler). Algoritmanın işe yaradığı söyleniyor lineer logaritmik zaman, Eğer T(n) = Ö( n kayıt n) . Böylece, lineer-logaritmik eleman lineer terimden daha hızlı büyür, fakat herhangi bir polinomdan daha yavaş büyür. n derece kesinlikle 1'den büyük.

Çoğu durumda, çalışma süresi n kayıt n basitçe Θ(log n) n bir Zamanlar. Örneğin, bir ikili ağaçla sıralama, her öğeyi birbiri ardına n boyutunda bir diziye ekleyerek bir ikili ağaç oluşturur. Çünkü yerleştirme işlemi dengeli ikili arama ağacı O(günlük n), algoritmanın toplam yürütme süresi doğrusal-logaritmik olacaktır.

Karşılaştırma türleri log( n!) = Θ( n kayıt n) Stirling formülüne göre. Aynı çalışma zamanı genellikle özyinelemeli denklemden kaynaklanır. T(n) = 2 T(n/2) + O( n).

kare altı zaman

Polinom zaman algoritmalarına bazı örnekler:

Kesin ve zayıf polinom zamanı

Bazı bağlamlarda, özellikle optimizasyonda, algoritmalar arasında bir ayrım yapılır. katı polinom zamanı ve zayıf polinom zamanı. Bu iki kavram yalnızca tam sayılardan oluşan girdiler için geçerlidir.

Kesin olarak polinom zamanı, aritmetik hesaplama modelinde tanımlanır. Bu modelde, temel aritmetik işlemler (toplama, çıkarma, çarpma, bölme ve karşılaştırma), işlenenlerin uzunluğuna bakılmaksızın yürütme birimleri olarak alınır. Algoritma, aşağıdaki durumlarda kesinlikle polinom zamanında çalışır:

aritmetik hesaplama modelindeki işlem sayısı, giriş akışındaki tamsayıların sayısındaki bir polinomla sınırlıdır ve
Algoritma tarafından kullanılan bellek, giriş boyutlarında bir polinomla sınırlandırılır.

Bu iki özelliğe sahip herhangi bir algoritma, bir Turing makinesinde aritmetik işlemleri gerçekleştirmek için aritmetik işlemleri karşılık gelen algoritmalarla değiştirerek bir polinom zaman algoritmasına indirgenebilir. Yukarıdaki gereksinimlerin ikincisi karşılanmazsa, bu artık doğru olmayacaktır. Bir tamsayı (bir Turing makinesinde n ile orantılı bellek kaplar) verildiğinde, tekrarlanan "üs alma" kullanılarak n işlemde hesaplanabilir. Ancak, temsil etmek için kullanılan bellek 2 2 n (\displaystyle 2^(2^(n))), orantılı 2 n (\displaystyle 2^(n)), ve giriş için kullanılan belleğe polinomdan ziyade üstel olarak bağlıdır. Bu nedenle - bu hesaplamaları bir Turing makinesinde polinom zamanında yapmak imkansızdır, ancak polinom sayıda aritmetik işlemde yapılabilir.

Tersine, Turing makinesinin adım sayısı için çalışan, ikili kodlanmış girişin polinom uzunluğu ile sınırlanan, ancak aritmetik işlem sayısı için çalışmayan, sayı sayısının polinomuyla sınırlı olan algoritmalar vardır. giriş. İki tamsayının en büyük ortak faktörünü hesaplamak için kullanılan Öklid algoritması buna bir örnektir. iki tamsayı için a (\görüntüleme stili a) ve b (\görüntüleme stili b) algoritmanın çalışma süresi sınırlıdır O ((log ⁡ a + log ⁡ b) 2) (\displaystyle O((\log \ a+\log \ b)^(2))) Turing makinesinin adımları. Bu sayı, sayıların ikili gösteriminin boyutunda bir polinomdur. a (\görüntüleme stili a) ve b (\görüntüleme stili b) kabaca şu şekilde temsil edilebilir log ⁡ a + log ⁡ b (\displaystyle \log \a+\log \b). Aynı zamanda, aritmetik işlemlerin sayısı, girdideki tam sayıların sayısıyla sınırlandırılamaz (bu durumda bir sabittir - girdide yalnızca iki sayı vardır). Bu açıklama ışığında, algoritma katı polinom zamanında çalışmaz. Algoritmanın gerçek çalışma süresi değerlere bağlıdır. a (\görüntüleme stili a) ve b (\görüntüleme stili b), sadece girdideki tam sayıların sayısı değil.

Bir algoritma polinom zamanında çalışıyorsa ancak tam olarak polinom zamanında çalışmıyorsa, çalıştığı söylenir. zayıf polinom zamanı. Zayıf bir polinom algoritmasının bilindiği, ancak kesin olarak polinom bir algoritmanın bilinmediği bir problemin iyi bilinen bir örneği doğrusal programlamadır. Zayıf polinom zamanı, psödopolinom zamanı ile karıştırılmamalıdır.

Zorluk sınıfları

Polinom zaman kavramı, hesaplama karmaşıklığı teorisinde birkaç karmaşıklık sınıfına yol açar. Polinom zamanı kullanılarak tanımlanan bazı önemli sınıflar aşağıda listelenmiştir.

: Polinom zamanında deterministik bir Turing makinesinde çözülebilen çözülebilir problemlerin karmaşıklık sınıfı.
: Polinom zamanında deterministik olmayan bir Turing makinesinde çözülebilen çözülebilirlik problemlerinin karmaşıklık sınıfı.
ZPP: Olasılıklı bir Turing makinesinde polinom zamanında sıfır hata ile çözülebilen çözülebilirlik problemlerinin karmaşıklık sınıfı.
: Olasılıksal bir Turing makinesinde polinom zamanında tek taraflı hatalarla çözülebilen çözülebilirlik problemlerinin karmaşıklık sınıfı.
BPP polinom zamanında olasılıksal Turing makinesi.
BQP: Kuantum Turing makinesinde polinom zamanında iki taraflı hatalarla çözülebilen çözülebilirlik problemlerinin karmaşıklık sınıfı.

P, deterministik bir makinedeki en küçük zaman karmaşıklığı sınıfıdır. sürdürülebilir makinenin modelini değiştirmek açısından. (Örneğin, tek bantlı bir Turing makinesinden çok bantlı bir Turing makinesine geçmek ikinci dereceden bir hızlanma ile sonuçlanabilir, ancak bir modelde polinom zamanında çalışan herhangi bir algoritma diğerinde polinom zamanında çalışacaktır.)

süperpolinom zamanı

Algoritmanın işe yaradığı söyleniyor süperpolinom zamanı, Eğer T(n) yukarıda bir polinomla sınırlı değildir. Bu süre eşittir ω( n C) tüm sabitler için C, nerede n giriş argümanıdır, genellikle girişin bit sayısıdır.

Örneğin, 2 uygulayan bir algoritma n giriş boyutu için adımlar n süperpolinom zaman gerektirir (daha spesifik olarak, üstel zaman).

Üstel kaynakları kullanan bir algoritmanın süperpolinom olduğu açıktır, ancak bazı algoritmalar çok zayıf bir şekilde süperpolinomdur. Örneğin, test basitlik Adleman - Pomerance - Rumeli * zaman için çalışır n O(günlük günlüğü n) üzerinde n-bit girişi. Bu, yeterince büyük olması için herhangi bir polinomdan daha hızlı büyür. n, ancak küçük dereceli bir polinomun baskın olmaması için girdinin boyutu çok büyük olmalıdır.

Süperpolinom zamanı gerektiren bir algoritma karmaşıklık sınıfının dışındadır. Cobham tezi bu algoritmaların pratik olmadığını ve çoğu durumda öyle olduklarını savunuyor. Eşitlik sınıfları P ve NP problemi çözülmediği için, polinom zamanında NP-tam problemlerini çözmek için şu anda hiçbir algoritma bilinmemektedir.

yarı polinom zaman

algoritmalar yarı polinom zamanı polinom zamanından daha yavaş çalışan, ancak üstel zaman algoritmaları kadar yavaş olmayan algoritmalardır. Yarı polinom algoritması için en kötü durum çalışma süresi C. Bir tamsayıyı çarpanlara ayırmak için iyi bilinen klasik algoritma, , olumsuzlukçalışma süresi şu şekilde temsil edilemediğinden yarı polinomdur 2 O ((log ⁡ n) c) (\displaystyle 2^(O((\log n)^(c)))) bazı sabitler için C. Yarı polinom zaman algoritmasının tanımındaki "c" sabiti 1 ise polinom zaman algoritmasını, 1'den küçük ise alt lineer zaman algoritmasını alırız.

Yarı polinom zaman algoritmaları genellikle bir NP-zor problemi başka bir probleme indirgediğinde ortaya çıkar. Örneğin, NP-zor bir problemi, diyelim ki 3SAT alabilir ve onu başka bir problem B'ye indirgeyebilirsiniz, ancak problemin boyutu 2 O ((log ⁡ n) c) (\displaystyle 2^(O((\log n)^(c)))). Bu durumda, indirgeme, B probleminin NP-zor olduğunu kanıtlamaz, böyle bir indirgeme, 3SAT (ve ardından tüm -problemler için) için yarı polinom bir algoritma olmadığı sürece, yalnızca B için bir polinom algoritması olmadığını gösterir. Benzer şekilde, yarı polinom zamanlı algoritmaları bildiğimiz, ancak polinom zamanlı algoritmaların bilinmediği bazı problemler vardır. Bu tür problemler yaklaşıklık algoritmalarında ortaya çıkar. İyi bilinen bir örnek, yaklaşıklık katsayısına sahip bir yaklaşım yarı polinom algoritmasının bulunduğu yönlendirilmiş Steiner problemidir. O (log 3 ⁡ n) (\displaystyle O(\log ^(3)n))(burada n köşe sayısıdır), ancak bir polinom zaman algoritmasının varlığı açık bir problemdir.

zorluk sınıfı QP yarı polinom zaman algoritmalarına sahip tüm problemlerden oluşur. DTIME cinsinden şu şekilde tanımlanabilir:

QP = ⋃ c ∈ N DTIME (2 (log ⁡ n) c) (\displaystyle (\mbox(QP))=\bigcup _(c\in \mathbb (N) )(\mbox(DTIME))(2^ ((\log n)^(c))))

NP-Tam Problemlerle İlişkisi

Karmaşıklık teorisinde, çözülmemiş P ve NP sınıflarının eşitliği problemi, NP sınıfındaki tüm problemlerin polinom zamanlı çözüm algoritmalarına sahip olup olmadığını sorar. 3SAT gibi NP-tamamlanmış problemler için iyi bilinen tüm algoritmalar üstel zamana sahiptir. Ayrıca, birçok doğal NP-tam problem için alt-üssel yürütme süresine sahip algoritmaların olmadığı varsayımı vardır. Burada "alt-üssel zaman" aşağıda verilen ikinci tanım anlamında alınmıştır. (Öte yandan, komşuluk matrisleri tarafından doğal olarak temsil edilen birçok çizge teorisi problemi, sadece girdinin boyutu köşelerin sayısının karesi olduğu için üssel zamanda çözülebilir.) Bu varsayım (k-SAT problemi için) olarak bilinir. üstel zaman hipotezi. NP-tamamlanmış problemlerin yarı-polinom zaman algoritmalarına sahip olmadığını varsaydığından, yaklaşım algoritmaları alanındaki bazı yakınlaştırılamayan sonuçlar, NP-tam problemlerin yarı-polinom zaman algoritmalarına sahip olmadığını varsayar. Örneğin, küme kaplama probleminin yakınlaştırılamamasıyla ilgili iyi bilinen sonuçlara bakın.

üssel zaman

Terim alt üstel zaman bazı algoritmaların çalışma süresinin herhangi bir polinomdan daha hızlı büyüyebileceğini, ancak üstelden önemli ölçüde daha az kaldığını ifade etmek için kullanılır. Bu anlamda, alt-üssel zamanlı algoritmalarla ilgili problemler, yalnızca üstel zamanlı algoritmalardan daha dövülebilirdir. "Üslü alt"ın tam tanımı henüz evrensel olarak kabul edilmemiştir ve en yaygın iki tanımı aşağıda veriyoruz.

İlk tanım

Çalışma süresinin logaritması verilen herhangi bir polinomdan daha az büyüyen bir algoritma ile çözülen bir problemin alt-üssel zamanda çözüldüğü söylenir. Daha kesin olarak, herhangi bir ε > 0 için problemi O(2 n ε) zamanında çözen bir algoritma varsa, bir problemin üssel zamanı vardır. Tüm bu tür problemlerin kümesi karmaşıklık sınıfını oluşturur. ALT EXP, ki bu DTIME cinsinden olarak ifade edilebilir .

SUBEXP = ⋂ ε > 0 DTIME (2 n ε) (\displaystyle (\text(SUBEXP))=\bigcap _(\varepsilon >0)(\text(DTIME))\left(2^(n^(\varepsilon) ))\sağ))

Burada ε'nin giriş verilerinin bir parçası olmadığına ve her ε'nin problemi çözmek için kendi algoritmasına sahip olabileceğine dikkat edin.

İkinci tanım

Bazı yazarlar, alt üstel süreyi çalışma süresi olarak tanımlar 2 o( n) . Bu tanım, ilk tanımdan daha uzun bir çalışma süresi sağlar. Böyle bir alt-üssel zaman algoritmasının bir örneği, tam sayıları çarpanlara ayırmaya yönelik iyi bilinen klasik algoritma, yaklaşık olarak çalışan genel sayı alanı elek yöntemidir. 2 O ~ (n 1 / 3) (\displaystyle 2^((\tilde (O))(n^(1/3)))), giriş uzunluğunun olduğu yerde n. Başka bir örnek, iyi bilinen algoritmadır. grafik izomorfizm problemleri, kimin çalışma süresi 2 O ((n log ⁡ n)) (\displaystyle 2^(O((\sqrt (())n\log n)))).

Algoritmanın köşe sayısında veya kenar sayısında alt-üslü olup olmadığı arasında bir fark olduğuna dikkat edin. V parametreli karmaşıklık bu fark, çifti, çözülebilirlik problemini ve parametreyi belirterek açıkça mevcuttur. k. SUBEPT içinde üstel zamanda çalışan tüm parametreli problemlerin sınıfıdır. k ve polinom için n :

SUBEPT = DTIME (2 o (k) ⋅ poli (n)) . (\displaystyle (\text(SUBEPT))=(\text(DTIME))\left(2^(o(k))\cdot (\text(poly))(n)\sağ).)

Daha doğrusu, SUBEPT, tüm parametreli görevlerin sınıfıdır. (L , k) (\displaystyle (L,k)), bunun için hesaplanabilir bir fonksiyon var f: N → N (\displaystyle f:\mathbb (N) \to \mathbb (N) )İle f ∈ o (k) (\displaystyle f\in o(k)) ve çözen bir algoritma L sırasında 2 f (k) ⋅ poli (n) (\displaystyle 2^(f(k))\cdot (\text(poly))(n)).

Bölüm 2. Algoritmaların karmaşıklığı.

2.1 Algoritmaların zaman ve hesaplama karmaşıklığı.

Algoritmanın zaman karmaşıklığı (T(n) , nerede n– görev boyutu), adım adım ölçülen algoritmanın yürütme süresidir (sonuca ulaşmak için yürütülmesi gereken algoritma talimatları). Yani, bu, sorunu çözmek için algoritmayı oluşturan temel işlemlerin sayısıdır (:=,<>, =, +, –, *, /; ve, veya, değil, xor; aramak, geri dönmek).

Problemi çözerken girdi verilerinin kombinasyonuna bağlı olan üç tür zaman karmaşıklığı vardır (eşdeğerlik, seyreklik, düzenlilik ve girdi verilerinin diğer özellikleri).

https://pandia.ru/text/78/183/images/image002_151.gif" width="178 height=60" height="60">

Olay T(n)= C* n2 kare matris için geçerlidir.

Bu durumda temel işlemler "+" ve "*" kombinasyonudur.

Orijinal matris kimlik ise, En İyi Durumu elde ederiz.

Matristeki elemanların yarısı 0, yarısı 1 ise, Ortalama Durum elde edilir.

Devamlı İLE tam olarak ifade edilemeyen , dış faktörlerin algoritmaların yürütme süresi üzerindeki etkisini (bilgisayar hızı, derleme hızı) karakterize eder. Bu nedenle, algoritmaların zaman karmaşıklığını tahmin etmek için zaman birimlerinin kullanılması tamamen doğru değildir. Bu durumda, matris-vektör çarpma algoritmasının zaman karmaşıklığının orantılı olduğu söylenir. n2 .

2.2 Öve Ω notasyonlardır.

Artarken zaman karmaşıklığının davranışının doğası n (n® ¥ ) aranan algoritmanın asimptotik karmaşıklığı.

Asimptotik karmaşıklığın büyüme oranını tanımlamak için şunu kullanırız: O notasyonu. Bir algoritmanın zaman karmaşıklığının sıralı olduğu söylendiğinde n2 :

T(n)= Ö(n2 )= Ö(F(n)),

Bu, pozitif sabitlerin olduğu anlamına gelir. C, n0=const (C>0), öyle ki herkes için n ³ n0 eşitsizlik

T(n) £ C* F(n)

Bu, karmaşıklık tahmininin üst sınırıdır.

Örnek 2:

İzin vermek T(0)=1, T(1)=4, …, T(n)=(n+1)2, o zaman bu algoritmanın zaman karmaşıklığı bir büyüme sırasına sahiptir T(n)= Ö(n2 ).

gösterilebilir ki, hepsi için n > n0 de n0 = 1, C = 4 eşitsizlik (1) tutar.

(n+1)2 £ 4* n2

Örnek 3:

Zaman karmaşıklığı bir polinom olarak yazılırsa

T(n)= C1 n2 + C2 n+ C3 ,

o zaman böyle bir algoritma, polinomun maksimum elemanının derecesinin bir katı olan bir karmaşıklık sırasına sahiptir, çünkü en hızlı şekilde büyür. n® ¥ :

T(n)= Ö(n2 ).

Örneğin:

3 n2 +5 n+1 £ 5 n2

" n ³ 1

Örnek 4:

Bazı algoritmaların karmaşıklığı birden fazlaysa 3 n, o zaman hızın büyüme sırasının bir katı olamayacağı gösterilebilir. Ö(2 n):

T(n)=3 n¹ Ö(2 n).

Sabitler olsun C, n0 , öyle ki aşağıdaki eşitsizlik geçerlidir:

3n £ C*2 n, n > n0 .

Buradan şunu elde ederiz:

İLE³ (3/2)2, n > n0 .

Ama şu anda n® ¥ öyle bir sabit yok İLE bu eşitsizliği tatmin eder.

Karmaşıklığın üst sınırına ek olarak, zaman karmaşıklığının büyüme hızında da bir alt sınır vardır:

T(n) ³ W(F(n))

Eşitsizlik (2), bazı sabitlerin olduğu anlamına gelir. İLE, hangisi için n® ¥ zaman karmaşıklığı

T(n) ³ C* F(n).

T(N)'yi (asimptotik zaman karmaşıklığı) doğru bir şekilde belirlemenin zorluğu göz önüne alındığında, ilk verilerin boyutuna bağlı olarak, pratikte, algoritmanın zaman karmaşıklığına ilişkin alt ve üst sınırlar kullanılır:

T(n) = Q (F(n))

Sabitin değerine bağlı olarak İLE algoritmanın karmaşıklığının büyüme hızı önemli ölçüde değişebilir.

Örnek 5:

Zaman karmaşıklığı şu şekilde yazılabilir:

T(N)=3n2 –100n+6=O(n2)

3n2 >3n2 –100n+6, n³ 1, C=3.

Eğer C1» 0 (С1=0,00001), o zaman eşitsizlik

10-5 n2 > 3 n2 –100 n+6, n³ 1

gerçekleştirilmez.

Ancak artan karmaşıklık sırasının

3n2 -100n+6¹ ÜZERİNDE).

C*N< 3N2, N>C.

3n2 –100n+6=(n2)

C=2.29, n ³ n0.

2.99* n2 < 3 n2 –100 n+6

Alt sınırın olduğu gösterilebilir.

3 n2 –100 n+6 ¹ W(n3 ) de C=1.

eşitsizlik 3 n2 –100 n+6 ³ n3 gerçekleştirilmez.

3 n2 –100 n+6= W(n)

C1 = , n> n0 .

https://pandia.ru/text/78/183/images/image007_89.gif" width="305" height="247 src=">

F1 (n)=100 n2

F2 (n)=5 n3

n0 =20 – kritik nokta.

Daha düşük karmaşıklık derecesine sahip algoritmaların tercih edilmesinin bir başka nedeni de, karmaşıklık derecesi ne kadar düşükse problem boyutunun o kadar büyük olmasıdır. n pratik olarak çözülebilir.

0 "style="margin-left:5.4pt;border-collapse:collapse;border:none">

Örnek 6:

Algoritmaların karmaşıklığında daha büyük bir büyüme sırasının, kural olarak daha küçük bir sabite sahip olduğu dikkate alınmalıdır. C1 sabit bir ile karakterize edilen küçük bir karmaşıklık büyüme düzeni ile karşılaştırıldığında C2.

Bu durumda, küçük veri boyutlarına sahip problemlerin çözümü için hızla artan karmaşıklığa sahip bir algoritma tercih edilebilir ( n® 0 ).

Aynı problemi karmaşıklıkla çözmek için beş algoritma verilsin:

A1: 100 n

A2: 100 n* logN

A3: 10 n2

A4: n3

A5: 2 n

Daha sonra sorunlar için n=2 ¸ 9 A5 daha hızlı olacaktır ( F(n) ~ 4 ¸ 512 ). Diğer algoritmalar, ikame sırasında önemli ölçüde daha düşük oranlar verecektir.

saat n=10 ¸ 58 A3 tercih edilir.

saat n=59 ¸ 1024 A2 en verimli olacaktır.

saat n>1024 A1 tercih edilir.

Birkaç sıralı veya paralel algoritmadan oluşan programlar için karmaşıklık şu şekilde tahmin edilir: toplam kuralı ve Ürün kuralı.

Toplam kuralı : Programın, karmaşıklıkların tanımlandığı, art arda yürütülen iki algoritma Р1 ve Р2'den oluşmasına izin verin. Ö(F(n)) ve Ö(G(n)) sırasıyla. Daha sonra tüm programın zaman karmaşıklığı, algoritmaların her birinin zaman karmaşıklığının toplamı olarak belirlenecektir:

T(n) = T1 (n)+ T2 (n)

Genel olarak şunları elde ederiz:

T(n)Þ O(maks f(n), g(n))

Sanat kuralı: Karmaşıklık sırasına göre paralel çalışan iki algoritmadan oluşan bir programın zaman karmaşıklığına izin verin Ö(F(n)) ve Ö(G(n)) sırasıyla, algoritmaların her birinin zaman karmaşıklığının ürünü olarak tanımlanır:

T(n) = T1 (n)* T2 (n)

Genel olarak:

T(n) Þ Ö(F(n)* G(n))

Logaritmalar.

2.3. özyineleme.

Algoritmik yapıların iç içe geçmesi nedeniyle özyinelemeli algoritmaların karmaşıklığını tahmin etmek kolay değildir.

F(n) Þ F(n* F(n-1))

Örneğin, algoritmayı tekrar tekrar değerlendirmek için n! Karmaşıklık, özyinelemeye dahil edilen algoritmaların her birinin karmaşıklığına bağlı olacaktır.

Genel olarak T(n) ~ Ö(n).

Diğer özyinelemeli algoritmalar genellikle zaman karmaşıklığına sahiptir T(n) ~ Ö(bir) , nerede a= const aynı sorunu çözmek için özyinelemeli olmayan bir algoritmanın karmaşıklığından daha büyük bir toplam karmaşıklıkla sonuçlanır.

2.4 Algoritmaların ve programların karmaşıklığının değerlendirilmesi.

2.4.2 Bağımlılık kurtarma algoritmaları.

Bazı durumlarda, programın yapısı bilinmemektedir ve yalnızca çeşitli boyutlardaki girdi verileri için çalışma süresini belirlemek mümkündür. T(n) (sn.)

Programın karmaşıklığının analitik bir bağımlılığını oluşturmak için işlevi değerlendirin T(n) belirli aralıklarla [ az dakika, Nmaks] . Daha sonra, bazı analitik fonksiyonların bulunan eğrisi, fonksiyonun parametrelerinde bir değişiklik ve yaklaşıklık hatasının bir tahmini ile yaklaştırılır.

Kural olarak, iyi bilinen zaman karmaşıklığı işlevleri şu şekilde kullanılır: Ö(n!), Ö(XN), Ö(NX), Ö(logN), Ö(https://pandia.ru/text/78/183/images/image010_72.gif" width="307" height="225 src=">Program üzerinde yapılan deney sonucunda bir zaman karmaşıklığı tablosu çıkarılmıştır. Elde edilen:

Fonksiyonun yaklaşık olarak aranmasının bir sonucu olarak, aşağıdaki analitik bağımlılık elde edildi:

https://pandia.ru/text/78/183/images/image012_68.gif" width="321" height="143 src=">

Örnek 2:

Aynı algoritmanın çalışma süresinin, görevin boyutuna ek olarak, kullanıcı tarafından girilen diğer parametrelerden etkilendiği sıklıkla görülür.

Bu durumda, bir yaklaşım fonksiyonları ailesi oluşturulur ve algoritmanın karmaşıklığı analitik olarak bulunur.

İş gücü girişi" href="/text/category/trudoemkostmz/" rel="bookmark"> İş gücü girişi (çalışma süresi).

Algoritmanın polinom veya üstel doğası, girdi veri temsilinin (ikili, ondalık veya diğer sayı sistemi) biçimine göre değişmezdir.

Bir algoritmanın çalışma süresi, yani zaman karmaşıklığı, yukarıdan bir dereceye kadar bir polinomla sınırlandırılıyorsa, polinom olduğu söylenir. T(n)= Ö(Nm) . Daha sonra, böyle bir algoritma tarafından çözülen tüm problemler, bir P-sınıfı problem oluşturur. Bu görevlerin R'ye dahil olduğunu söylüyorlar.

Zaman karmaşıklığı üstel olan problemler ( T(n)= Ö(Kn) ), R'ye dahil değildir.

Yorum Yap : Doğrusal karmaşıklığa sahip problemlerin P'ye dahil olduğu gösterilebilir.

T(n)= Ö(n1 )

Belirleyici olmayan bir algoritma kullanarak polinom zamanında çözülebilen bir NP problemi sınıfını tanıtalım.

Algoritmanın durumunu, şu anda yürütülmekte olan komutun adres kümesi ve işlemin durum vektörüne eşdeğer olan tüm değişkenlerin değerleri olarak tanımlayalım. Bu nedenle, çoğu algoritma deterministiktir, yani herhangi bir durum için içlerinde yalnızca bir kabul edilebilir sonraki durum vardır (koşul ve seçim işlemleri dahil). Bu, böyle bir algoritmanın aynı anda yalnızca bir şey yapabileceği anlamına gelir.

V deterministik olmayan algoritma (NDA) herhangi bir verili durum için birden fazla geçerli sonraki durum olabilir, yani böyle bir algoritma herhangi bir zamanda birden fazla ifade çalıştırabilir.

NDA, rastgele veya olasılıklı bir algoritma değildir. Birçok durumda olabilen bir algoritmadır (bu, bir problemi birçok seçeneğe paralel olarak çözmeye eşdeğerdir).

Örnek:

Bir deterministik algoritma (DA) bu sorunu sırayla çözecektir (tüm seçeneklerin numaralandırılması, A0 alternatifini seçene kadar optimallik kriteri K0 ile karşılaştırma).

NDA, aynı anda (paralel olarak) tüm alternatifleri elde edebilir ve K0 ile karşılaştırabilir, her alternatif için bağımsız olarak yürütülen ayrı bir süreç olarak kendini kopyalayabilir.

Bu durumda, herhangi bir kopya, yanlış bir sonuç alındığını veya sonucun alınmadığını tespit ederse, yürütmeyi durdurur. Kopya K0'ı karşılayan bir çözüm bulursa, başarılı olduğunu bildirir ve diğer tüm kopyalar çalışmayı durdurur.

O. NDA, üç parametre ile karakterize edilir:

1. tercih değerleri S kümesinin elemanları olan çok değerli bir fonksiyondur;

2. arıza algoritmanın kopyasının çalışmayı durdurmasına neden olur;

3. başarı algoritmanın tüm kopyalarının çalışmayı durdurmasına ve bir sonuç üretmesine neden olur.

Açıkçası, hiçbir fiziksel cihaz sınırsız deterministik olmayan davranışa sahip değildir, bu nedenle NDA teorik bir yöntemdir.

Bir polinom NDA kullanılarak çözülebilen problemler, bir NP problemleri sınıfını oluşturur.

2.5.2 NP-zor veNP- görevleri tamamlayın.

P'de yer alan görev, NP-zor, NP'de yer alan tüm problemlere bir çözüm elde etmek için kullanılabilecek çözümünün bir polinom DA'sı (PDA) varsa. Yani, böyle bir problem, en azından NP'deki herhangi bir problem kadar zorsa, NP-zordur.

NP'ye ait bir NP-zor probleme denir. NP-tam dolu görev. Bu tür problemler, NP'deki herhangi bir problemden daha az zor değildir. Aynı zamanda, NP-zor veya NP-tamamlanmış bir problem için bir PDA'nın varlığı, P ve NP sınıflarının çakıştığı, yani 3. sınıfın tüm problemlerinin hızlı bir algoritma ile çözülmesinin mümkün olduğu anlamına gelir.

Bir problemin NP-zor olduğunu kanıtlamak için, bir problem için bir PDA varsa, o zaman NP'deki problemleri çözmek için başka bir PDA elde etmek için kullanılabileceğini göstermek gerekir.

Bir problemin NP-tamamlanmış olduğunu belirlemek için, onun NP'ye ait olduğunu kanıtlamak gerekir.

Bir problemi çözmek için bir algoritma kullanarak diğerini çözmek için bir algoritma elde etme fikri, algoritma teorisindeki en önemli konulardan biridir.

tanım 1: Eğer P1 probleminin herhangi bir özel durumu polinom zamanında P2 probleminin özel bir durumuna dönüştürülebiliyorsa, Problem P1 problem P2'ye dönüştürülür. Daha sonra P1 çözümü, P2 probleminin belirli bir durumunun çözümünden polinom zamanında elde edilebilir.

https://pandia.ru/text/78/183/images/image024_39.gif" width="158 height=56" height="56">

Örneğin:

F2 (xi)=(x1 Ú x2 ) Ù ( ) Ù ()

mümkün değildir, çünkü herhangi bir xi F2 (xi)= YANLIŞ.

teorem :

Tatmin edilebilirlik sorunu NP tamamlandı.

xi seçimi(doğru, yanlış)

E(x1, x2, …, xN) ise başarılı

başka başarısız

P1 probleminin P2'ye dönüşümü kullanılarak, tatmin edilebilirlik probleminin sınırlı durumunun bile NP-tam olduğu gösterilebilir.

K-fizibilite .

K-satisfiability, CNF'deki herhangi bir tümcenin en fazla K mantıksal değişkeni içerdiği anlamına gelir.

Minimum durum K=3'tür. CNF'de temsil edilen bir Boole fonksiyonu için, fonksiyon polinom zamanında bulunabilir. E*(x2), her maddede en fazla üç değişken içerir. O zamanlar E yapılabilirse yapılabilir E*.

E* (x1 , x2 ,…, xn) ® E* (xi)

Bunu yapmak için, ayrılığın sırasını azaltma yöntemini kullanıyoruz.

(a1 Ú a2 Ú … Ú ak)=(a1 Ú a2 Ú z) Ù (a3 Ú a4 Ú … Ú ak Ú )

Yinelemeli bir ayrıştırma işlemi uygulayarak, elde edilebilir E*.

Bir çözüm algoritması bulun E* fonksiyonlardan daha kolay E. Ama aynı zamanda fizibiliteyi kanıtlamak E*, orijinal işlevin karşılanabilirliğini kanıtlayacağız E.

Özel durum: K=2'de fonksiyon E R'ye dahildir.

NP sınıfı problemlerin örnekleri aynı zamanda şu şekilde hizmet edebilir: grafiklerdeki görevler :

1) Yönlendirilmemiş bir grafiğin maksimum kliklerinin belirlenmesi (NP-zor problem).

2) Tam bir alt grafik belirleme problemi (NP-tam problem).

3) Yönsüz bir grafik için L kardinalitesinin tepe kapağının belirlenmesi (NP-tam problem).

4) Yönsüz bir grafiğin maksimum tepe kapaklarının belirlenmesi (NP-zor problem).

5) Bir grafik için bir Hamilton çevriminin varlığını belirleme problemi (NP-tam problem).

6) Gezgin satıcı problemi: Her bir köşede tek bir oluşumla bir grafik boyunca optimal hareketin belirlenmesi (NP-zor problem).

7) Zamanlama problemi (NP-tamamlanma problemi).

2.6 Algoritmik olarak çözülemeyen problemler

Sorunları paylaşın bekar ve cüsseli.

Örneğin:

5+7=? tek bir sorundur.

x+y=? büyük bir sorundur.

Temelde çözülemez olanlar, paradoksal nesneleri elde etmeye veya paradoksal nesnelerin varlığını ima edecek problemleri çözmeye yönelik algoritmalar olmalıdır.

Örneğin, paradokslar şunlardır:

Örnek 1:

Hilbert'in 10. problemi.

D. Hilbert 1901'de Diophantine denklemlerini çözerken şöyle bir problem ortaya koydu:

Rastgele bir Diophantine denklemi için bazı tamsayı çözümlerini belirleyen bir algoritma bulun

F(x, y, …)=0

Bu, tamsayı üsleri ve bilinmeyenler için tamsayı katsayıları olan bir polinomdur.

anxn+an-1xn-1+…+a2x2+a1x+a0=0

Yukarıdaki denklem için, herhangi bir tamsayı kökü olan belirli bir çözüm vardır. xi bir bölendir a0 . nerede a0 asal faktörlere ayrıştırın ve her faktörün kök ile uyumluluğunu kontrol edin.

1970 yılında, Leningrad matematikçisi Yu. Matiyasevich, bir Diophant denklemini genel biçimde çözmenin algoritmik imkansızlığını matematiksel olarak kanıtladı.

Örnek 2:

Fermat teoremi:

Böyle bir tam sayı yok a, B, s, n (n>2) , bunun için eşitlik

bir + milyar = cn

Bu teorem birçok değer için kanıtlanmıştır. n ve belirli durumlar için doğrulanmıştır, ancak teoremin genel bir kanıtı henüz oluşturulmamıştır.

Örnek 3:

Goldbach sorunu.

H. Holbach, sorunu 1742'de Euler'e yazdığı bir mektupta formüle etti:

Her tamsayı olduğunu kanıtlayın n³ 6 üç asal sayının toplamı olarak gösterilebilir

n= a+ B+ C

Bu, herhangi bir tamsayıya izin verecek bir algoritma bulmanız gerektiği anlamına gelir. n³ 6 üç asal terime en az bir ayrıştırma bulun.

Euler bu soruna sık sık bir çözüm önerdi: n bu problem çözülebilir ve iki basit terime ayrıştırmaya eşdeğerdir.

I. Vinogradov 1937'de bunun garip olduğunu kanıtladı nüç tane asal terim bulmak mümkün ama çift sayılar için çözüm şu ana kadar bulunamadı.

O(1) - Programdaki işlemlerin çoğu yalnızca bir kez veya yalnızca birkaç kez gerçekleştirilir. Sabit karmaşıklığın algoritmaları. Veri boyutundan bağımsız olarak her zaman aynı süreyi gerektiren herhangi bir algoritma, sürekli karmaşıklık.

ÜZERİNDE) - Program çalışma süresi lineer olarak genellikle girdi verilerinin her bir öğesinin yalnızca doğrusal sayıda işlenmesi gerektiğinde.

O(N 2), O(N 3), O(N a) - Polinom karmaşıklığı.

O(N 2)-kuadratik karmaşıklık, O(N 3)-kübik karmaşıklık

O(Günlük(N)) - Program çalışma zamanı logaritmik, program N arttıkça çok daha yavaş çalışmaya başlar.Bu tür çalışma süresi genellikle büyük bir problemi küçük problemlere bölen ve bunları ayrı ayrı çözen programlarda bulunur.

O(N*log(N)) - Böyle bir çalışma süresi şu algoritmalara sahiptir: büyük bir sorunu küçük olanlara bölmek ve sonra bunları çözdükten sonra çözümlerini bağlayın.

O(2 N) = Üstel karmaşıklık. Bu tür algoritmalar çoğunlukla kaba kuvvet adı verilen bir yaklaşımdan kaynaklanır.

Programcı, algoritmaları analiz edebilmeli ve karmaşıklıklarını belirleyebilmelidir. Bir algoritmanın zaman karmaşıklığı, kontrol yapılarının analizine dayalı olarak hesaplanabilir.

Döngüleri ve özyinelemeli çağrıları olmayan algoritmaların sürekli karmaşıklığı vardır. Özyineleme ve döngüler yoksa, tüm kontrol yapıları sabit karmaşıklık yapılarına indirgenebilir. Sonuç olarak, tüm algoritma aynı zamanda sabit karmaşıklık ile karakterize edilir.

Bir algoritmanın karmaşıklığını belirlemek temel olarak döngüleri ve özyinelemeli çağrıları analiz etmeye gelir.

Örneğin, dizi öğelerini işlemek için bir algoritma düşünün.
i için:=1'den N'ye
Başlamak
...
son;

Bu algoritmanın karmaşıklığı O(N)'dir, çünkü döngünün gövdesi N kez yürütülür ve döngü gövdesinin karmaşıklığı O(1)'dir.

Bir döngü diğerinin içine yerleştirilmişse ve her iki döngü de aynı değişkenin boyutuna bağlıysa, tüm yapı ikinci dereceden karmaşıklıkla karakterize edilir.
i için:=1'den N'ye
j:=1 ila N için
Başlamak
...
son;
Bu programın karmaşıklığı O(N 2)'dir.

var bir algoritmanın karmaşıklığını analiz etmenin iki yolu: aşağıdan yukarıya (içten dış kontrol yapılarına) ve Azalan (dıştan ve içten).

O(H)=O(1)+O(1)+O(1)=O(1);
O(I)=O(N)*(O(F)+O(J))=O(N)*O(koşul baskınlar)=O(N);
O(G)=O(N)*(O(C)+O(I)+O(K))=O(N)*(O(1)+O(N)+O(1))=O (N2);
O(E)=O(N)*(O(B)+O(G)+O(L))=O(N)* O(N 2)= O(N3);
O(D)=O(A)+O(E)=O(1)+ O(N 3)= O(N 3)

Bu algoritmanın karmaşıklığı O(N 3)'tür.

Kural olarak, bir programın çalışma zamanının yaklaşık %90'ı tekrar gerektirir ve yalnızca %10'u gerçek hesaplamadır. Programların karmaşıklığının bir analizi, hangi parçaların bu %90'a düştüğünü gösterir - bunlar en büyük yuvalama derinliğinin döngüleridir. Tekrarlar, iç içe döngüler veya iç içe özyineleme olarak düzenlenebilir.

Bu bilgiler programcı tarafından aşağıdaki şekilde daha verimli bir program oluşturmak için kullanılabilir. Her şeyden önce, tekrarların yuvalama derinliğini azaltmayı deneyebilirsiniz. Ardından, en iç içe döngülerdeki ifadelerin sayısını azaltmayı düşünün. Yürütme süresinin %90'ı iç döngülerin yürütülmesiyse, bu küçük bölümlerde %30'luk bir azalma, tüm programın yürütme süresinde %90 * %30 = %27'lik bir azalmayla sonuçlanır.

Bu en basit örnek.

Matematiğin ayrı bir bölümü, algoritmaların etkinliğinin analizi ile ilgilenir ve en uygun işlevi bulmak o kadar kolay değildir.

hadi değerlendirelim dizide ikili arama algoritması - ikilik.

Algoritmanın özü: dizinin ortasına gideriz ve anahtarın ortadaki öğenin değerine karşılık gelmesini ararız. Bir eşleşme bulamazsak, ortadaki öğenin göreceli anahtar boyutuna ve değerine bakarız ve ardından listenin alt veya üst yarısına gideriz. Bu yarıda yine ortayı ararız ve tekrar anahtarla karşılaştırırız. Çalışmazsa, mevcut aralığı tekrar yarıya böleriz.

fonksiyon arama(düşük, yüksek, anahtar: tamsayı): tamsayı;
var
orta, veri: tamsayı;
başlamak
düşük iken<=high do
başlamak
orta:=(düşük+yüksek) div 2;
veri:=a;
anahtar=veri ise
arama:=orta
Başka
eğer anahtar< data then
yüksek:=orta-1
Başka
düşük:=orta+1;
son;
arama:=-1;
son;

Döngünün ilk yinelemesi tüm listeyle ilgilidir. Sonraki her yineleme, alt listenin boyutunu yarıya indirir. Böylece, algoritma için listenin boyutları

n n/2 1 n/2 2 n/2 3 n/2 4 ... n/2 m

Sonunda öyle bir m tamsayısı olacak ki

n/2m<2 или n<2 m+1

m, n/2 m olan ilk tam sayı olduğundan<2, то должно быть верно

n/2 m-1 >=2 veya 2 m =

Bunu takip ediyor
2 metre = Eşitsizliğin her bir bölümünün logaritmasını alıyoruz ve
m= m değeri, = olan en büyük tamsayıdır<х.
Yani, O(log 2 n).

Genellikle çözülmekte olan problemin doğal bir "boyutu" (genellikle işlediği veri miktarı) vardır ve buna N adını veririz. Sonuç olarak, programın N boyutundaki verileri işlemesi için geçen süre için bir ifade elde etmek isteriz. N'nin işlevi. Genellikle, ortalama durumla ilgilenmiyoruz - programın "tipik" girdilerde beklenen çalışma süresi ve en kötü durum, programın olası en kötü girdilerde beklenen çalışma süresidir.

Bazı algoritmalar, ortalama ve en kötü durumlar için kesin matematiksel formüllerin bilinmesi anlamında iyi anlaşılmıştır. Bu tür formüller, matematiksel özellikler açısından çalışma süresini bulmak için programları dikkatlice inceleyerek ve ardından matematiksel analizlerini yaparak geliştirilir.

Bu tür bir analizin birkaç önemli nedeni şunlardır:
1. Üst düzey bir dilde yazılmış programlar makine kodlarına çevrilir ve belirli bir ifadeyi yürütmenin ne kadar süreceğini anlamak zor olabilir.
2. Birçok program girdi verilerine çok duyarlıdır ve bunların etkinliği onlara çok bağlı olabilir. Ortalama durum, programın kullanıldığı verilerle ilgisi olmayan matematiksel bir kurgu olabilir ve en kötü durum olası değildir.

En iyi, ortalama ve en kötü durumlar sıralamada çok büyük rol oynar.
Sıralama sırasındaki hesaplamaların miktarı

O-karmaşıklık analizi birçok pratik uygulamada yaygınlaşmıştır. Ancak, sınırlamaları açıkça anlaşılmalıdır.

İLE yaklaşımın ana eksiklikleri aşağıdakileri içerebilir:
1) karmaşık algoritmalar için, kural olarak O-tahminleri elde etmek ya çok zahmetlidir ya da neredeyse imkansızdır,
2) "ortalama olarak" karmaşıklığı belirlemek genellikle zordur,
3) O-tahminleri, algoritmalar arasındaki daha ince farklılıkları yansıtamayacak kadar kabadır,
4) O-analiz, az miktarda veri işlerken algoritmaların davranışını analiz etmek için çok az bilgi sağlar (veya hiç bilgi vermez).

O-notasyonundaki karmaşıklığı belirlemek, önemsiz bir görev olmaktan uzaktır. Özellikle, ikili aramanın verimliliği, döngülerin iç içe geçme derinliği ile değil, her ardışık girişimin seçilme şekli ile belirlenir.

Diğer bir zorluk ise "ortalama durum" tanımıdır. Algoritmanın çalışma koşullarını tahmin etmenin imkansızlığı nedeniyle genellikle bunu yapmak oldukça zordur. Bazen bir algoritma, büyük, karmaşık bir programın parçası olarak kullanılır. Bazen donanımın ve/veya işletim sisteminin veya derleyicinin bazı bileşenlerinin performansı, algoritmanın karmaşıklığını önemli ölçüde etkiler. Genellikle aynı algoritma birçok farklı uygulamada kullanılabilir.

Bir algoritmanın "ortalama olarak" zaman karmaşıklığını analiz etmeyle ilgili zorluklar nedeniyle, genellikle en kötü ve en iyi durumlar için tahminlerle yetinmek gerekir. Bu puanlar esasen "ortalama" karmaşıklığın alt ve üst sınırlarını tanımlar. Aslında, algoritmanın karmaşıklığını "ortalama olarak" analiz etmek mümkün değilse, Murphy yasalarından birini izlemeye devam eder, buna göre en kötü durum için elde edilen tahmin, "ortalama olarak" karmaşıklığın iyi bir tahmini olarak hizmet edebilir. ".

Belki de O-fonksiyonlarının ana dezavantajı aşırı pürüzlülükleridir. Algoritma A bir görevi 0.001*N s'de tamamlarsa, Algoritma B bunu çözmek için 1000*N s alırsa, B A'dan bir milyon kat daha hızlıdır. Bununla birlikte, A ve B aynı zamanda O(N) karmaşıklığını paylaşır.

Bu dersin çoğu, algoritmaların zaman karmaşıklığının analizine ayrılmıştı. Unutulmaması gereken başka karmaşıklık biçimleri de vardır: uzamsal ve entelektüel karmaşıklık.

Bir programı yürütmek için gereken bellek miktarı olarak alan karmaşıklığı daha önce belirtilmişti.

Bir algoritmanın entelektüel karmaşıklığını analiz ederken, algoritmaların anlaşılabilirliği ve geliştirmelerinin karmaşıklığı araştırılır.

Her üç karmaşıklık biçimi de genellikle birbiriyle ilişkilidir. Kural olarak, iyi bir zaman karmaşıklığı tahmini olan bir algoritma geliştirirken, uzaysal ve/veya entelektüel karmaşıklığından fedakarlık etmek gerekir. Örneğin, hızlı sıralama algoritması, seçim sıralama algoritmasından önemli ölçüde daha hızlıdır. Artan sıralama hızının getirisi, sıralama için gereken daha fazla bellek açısından gelir. Hızlı sıralama için ek belleğe duyulan ihtiyaç, birden çok özyinelemeli çağrıdan kaynaklanmaktadır.

Hızlı sıralama algoritması, eklemeli sıralama algoritmasına kıyasla daha fazla entelektüel karmaşıklık ile de karakterize edilir. Yüz kişiden bir dizi nesneyi sıralamasını isterseniz, büyük olasılıkla çoğu seçmeli sıralama algoritmasını kullanır. Ayrıca herhangi birinin hızlı sıralama kullanması da olası değildir. Hızlı sıralamanın daha büyük entelektüel ve uzamsal karmaşıklığının nedenleri açıktır: algoritma özyinelemelidir, onu açıklamak oldukça zordur, algoritma daha basit sıralama algoritmalarından daha uzundur (yani program metni).

Aynı sorunu çözmek için birden fazla algoritma bulmak çoğu zaman mümkündür. Bu bağlamda şu soru ortaya çıkıyor: algoritmalardan hangisi “daha iyi”?

Çoğu durumda, görünüşe göre, “daha iyi”, aynı girdi verilerinde, daha az bilgi işlem kaynağı (bellek ve zaman) tüketerek sorunun çözümüne gelen bir algoritmadır. Bu, elbette, gevşek bir tartışma. Daha titiz bir akıl yürütme için birkaç kavram sunuyoruz.

Bir algoritmanın hesaplama süreci, bazı girdiler için algoritma yürütülürken atılan bir dizi adımdır.

Algoritmanın kendisi ile bu algoritma tarafından oluşturulan hesaplama süreci arasındaki farkı anlamak önemlidir. İlki sadece tanım ikinci.

Bir algoritmanın zaman karmaşıklığı, bazı girdiler için algoritmanın hesaplama sürecini tamamlamak için gereken \(T\) zamandır.

Yürütme süresinin belirli bir sanatçıya bağlı olduğu açıktır. Diyelim ki bir elektronik hesap makinesi ve bir süper bilgisayar muhtemelen aynı algoritmayı farklı zamanlarda yürütecek.

Bununla birlikte, \(T\) süresi, \(k\) temel eylemlerin sayısı ve bir temel eylemin \(t\) ortalama yürütme süresi cinsinden ifade edilebilir:

Ayrıca, \(k\) bir özelliktir çoğu algoritma ve \(t\) yürütücünün bir özelliğidir.

\(t\)'nin belirli bir icracı için bir sabit olarak kabul edilebileceği gerçeği göz önüne alındığında, genellikle algoritmaların karmaşıklığı sabit bir faktöre kadar tahmin edilir. Başka bir deyişle, algoritmanın karmaşıklığı tahmin edilir. büyüme sırası.

Büyüme sırası Bir pozitif tanımlı fonksiyon \(g(x)\) bir büyüme sırasına sahiptir \(f(x)\) ( \(g(x)=\mathcal(O)(f(x))\) ) Eğer \(\vardır c>0: \: \forall x>x_0, \, g(x) \leq c f(x)\).

Girilen verilere bağlı olarak, algoritma farklı zamanlarda çalışabilir. Genellikle derecelendirildi ortalama zorluk ve karmaşıklık en kötü ihtimalle. bağımlılık da var miktarları veri girişi \(n\) . Genellikle değerlendirilen, \(n\)'den gelen büyüme sırasıdır.

Bu nedenle, örneğin, verileri okumak ve bir dizi olarak bellekte depolamak, \(\mathcal(O)(n)\) karmaşıklığına sahip olacaktır veya doğrusal karmaşıklık, ve matris çarpımı zaten kübik\(\matematik(O)(n^3)\) .

Algoritmanın zaman karmaşıklığına ek olarak, aynı zamanda önemlidir. uzaysal algoritmanın karmaşıklığı.

Algoritmanın uzamsal karmaşıklığı sayıdır. ek olarak Algoritmanın çalışması için gereken bellek \(S\) . Giriş verilerini depolamak için gerekli olan \(D\) hafızası \(S\)'ye dahil değildir.

\(S\) genellikle yürütme aygıtına da bağlıdır. Diyelim ki, iki yürütme birimi sırasıyla 4 ve 8 baytlık tam sayıları destekliyorsa, algoritmanın 8 baytlık tam sayılardaki alan karmaşıklığı, 4 baytlık tam sayılardakinden iki kat daha fazla olacaktır. Bu nedenle, uzaysal karmaşıklık da büyüme sırasına göre tahmin edilir.

Algoritmaların karmaşıklık sınıfları

Belirli karmaşıklık sınıfları: Bunlar benzer zorluğa sahip kategorilerdir.

Aşağıdaki ana karmaşıklık sınıfları vardır:

DTIME Bir Turing makinesi, bir probleme sonlu bir sürede (adım sayısı) bir çözüm bulur. Algoritmanın asimptotikleri genellikle iyileştirilir, bu nedenle, örneğin, çalışma süresinin büyüme sırası \(T(n) = \mathcal(O)(f(n))\) ise, o zaman \(DTIME(f) (n))\) belirtilir. P Turing makinesi, probleme polinom zamanında (adım sayısı) bir çözüm bulur, yani. \(T(n) = \mathcal(O)(n^k)\) , burada \(k\in \mathbb(N)\) . \(P=DTIME(n^k)\) EXPTIME Turing makinesi problemin çözümünü üstel zamanda (adım sayısı), yani. \(T(n) = \matematik(O)(2^(n^k))\), burada \(k\in \mathbb(N)\) . \(EXPTIME=DTIME(2^(n^k))\) . DSPACE Bir Turing makinesi, sınırlı miktarda fazladan bellek (hücre) kullanarak bir soruna çözüm bulur. Algoritmanın asimptotikleri genellikle iyileştirilir, bu nedenle, diyelim ki, bellek tüketiminin büyüme sırası \(S(n) = \mathcal(O)(f(n))\) ise, o zaman \(DSPACE(f() n))\) belirtilir. L Turing makinesi, logaritmik uzay karmaşıklığı olan bir probleme çözüm bulur, ör. \(S(n) = \mathcal(O)(\log n)\). \(L=DSPACE(\log n)\) . PSPACE Turing makinesi, polinom uzay karmaşıklığı ile ilgili bir soruna bir çözüm bulur, yani \(S(n) = \mathcal(O)(n^k)\) , burada \(k\in \mathbb(N)\) . \(PSPACE=DSPACE(n^k)\) . EXPSPACE Turing makinesi, üstel uzay karmaşıklığı olan bir soruna bir çözüm bulur, yani. \(S(n) = \matematik(O)(2^(n^k))\), burada \(k\in \mathbb(N)\) . \(EXPSPACE=DSPACE(2^(n^k))\) .

Ayrıca kavramla çalışan teorik karmaşıklık sınıfları da vardır. kararsız Turing makineleri (HMT). Tanımları, Turing makinesinin yerini HMT ile değiştirdiği yukarıdaki ile aynıdır ve D'nin N ile değiştirildiği NTIME ve NSPACE dışında adların önüne N (örneğin, NP) eklenir.

NMT, çalışma prensiplerine göre MT'ye benzeyen tamamen teorik bir yapıdır, ancak fark, her bir durum için olabilir. birkaç olası eylemler. Aynı zamanda, NMT her zaman olası eylemlerden mümkün olan en az sayıda adımda bir çözüme yol açanı seçer. Eşdeğer olarak, HMT hesaplar Tümü dallanır ve mümkün olan en az sayıda adımda çözüme götüren dalı seçer.

Bazen kuantum bilgisayarların NMT'nin bir uygulaması olduğunu duyabilirsiniz. Bu, bazı durumlarda doğru gibi görünse de, genel olarak NMT, bir kuantum bilgisayardan daha güçlü bir sistemdir.

olduğu biliniyor \(P \subseteq NP \subseteq PSPACE \subseteq EXPTIME \subseteq NEXPTIME \subseteq EXPSPACE\)

Ayrıca, \(P \subsetneq EXPTIME\) , \(NP \subsetneq NEXPTIME\) , \(PSPACE \subsetneq EXPSPACE\)

\(P = NP\) ise \(EXPTIME = NEXPTIME\) olduğu da bilinmektedir.

P ve NP'nin eşitliği sorunu, modern bilgisayar biliminin çözülmemiş ana sorunlarından biridir.

Algoritma Örnekleri

Basit algoritmalara bazı örnekler verelim ve karmaşıklıklarını ele alalım.

Tamsayı gücüne yükseltme

Bu algoritma, çağımızdan önce eski Hindistan'da tanımlanmıştır ve gerçek bir sayının \(x\) doğal gücünü \(n\) hesaplamak için kullanılır.

\(n\)'yi ikili olarak yazın
Bu girişte 1'lerin her birini bir çift KX harfiyle ve her 0'ı K harfiyle değiştirin
En soldaki CH çiftinin üzerini çizin
Alınan dizeyi soldan sağa okumak, K harfini karşılamak, sonucun karesini almak ve X harfini karşılamak, sonucu x ile çarpın. Başlangıçta, sonuç x'tir.

Bu algoritmada, en iyi durumda \(n\) ve en kötü durumda \(2(n-1)\) ikili basamak sayısına eşit çarpma sayısına sahibiz. Her durumda, zaman karmaşıklığı .

Algoritmanın verimli bir şekilde uygulanmasında pratik olarak ek bellek gerekli değildir ve giriş verilerine bağlı değildir, bu nedenle alan karmaşıklığı \(S(n) = \mathcal(O)(1)\) şeklindedir.

Daha verimli algoritmalar olduğuna dikkat edilmelidir. Bununla birlikte, \(\mathcal(O)(n)\) çarpma işlemlerini gerektiren “naif” uygulama ile karşılaştırıldığında, bu algoritma nispeten verimlidir.

tamsayı çarpma

Bu çarpma algoritması, eski Mısır'da bilinmesine rağmen bazen Rus veya köylü olarak adlandırılır.

Birinci faktör art arda iki ile çarpılır ve ikincisi 2'ye bölünür. Sonuçlar, ikincisi 1 olana kadar iki sütuna yazılır.

Çarpmanın sonucu, ikinci sütundaki tek sayıların karşısındaki birinci sütundaki sayıların toplamıdır.

Tamsayı bölme ve 2 ile çarpma bir kaydırma ile gerçekleştirilebildiğinden, bu algoritma \(2 \log_2 n\) kaydırma işlemleri verir, burada \(n\) iki sayıdan küçüğüdür. En kötü durumda, \(\log_2 n - 1\) ekleme işlemleri de elde edilir. Her durumda, zaman karmaşıklığı \(T(n) = \mathcal(O)(\log n)\).

Algoritmanın verimli bir şekilde uygulanması için, ek bellek pratik olarak gerekli değildir ve giriş verilerine bağlı değildir, bu nedenle \(S(n) = \mathcal(O)(1)\)

Yine belirtmek gerekir ki daha verimli algoritmalar vardır. Bununla birlikte, \(\mathcal(O)(n)\) toplama işlemleri gerektiren "naive" uygulama ile karşılaştırıldığında, bu algoritma nispeten verimlidir.

Örnek

23 ile 43'ü çarpın.

23'ü ikinci faktör olarak alalım.

43	23	garip
86	11	garip
172	5	garip
344	2
688	1	garip

Sonuç \(43+86+172+688 = 989\)

10 vardiya işlemimiz ve 4 ekleme işlemimiz var. Başvuru için, \(\log_2(23) \yaklaşık 4,52\) .

Bir Algoritmanın Karmaşıklığını Belirleme

Asimptotik analizde elde edilen karmaşıklık fonksiyonunun tahmini, algoritmanın karmaşıklığı olarak adlandırılır.

Algoritmanın karmaşıklığının birkaç tahmini olduğu akılda tutulmalıdır.

Karmaşıklık fonksiyonunun asimptotik davranışı, işlemsel karmaşıklıktır. Buna ek olarak, aşağıdaki zorluk türlerini belirtebilirsiniz.

Geçici karmaşıklık - uzunluktaki giriş verilerinde algoritmanın çalışma süresinin asimptotik bir tahmini P. Açıkçası, hesaplama prosedürlerinin paralelleştirilmesinin yokluğunda, algoritmanın çalışma süresi, gerçekleştirilen işlemlerin sayısı tarafından benzersiz bir şekilde belirlenir. İşlemlerin süresini ifade eden sabit katsayılar, zaman karmaşıklığının sırasını etkilemez, bu nedenle operasyonel ve zaman karmaşıklığı formülleri genellikle birbiriyle çakışır.

kapasitif karmaşıklık - uzunluk giriş verilerinde algoritma yürütülürken eşzamanlı olarak var olan skaler sayısının asimptotik bir tahmini P.

Yapısal karmaşıklık - algoritmadaki kontrol yapılarının sayısının ve göreceli konumlarının özelliklerinin bir özelliği.

bilişsel karmaşıklık - uygulama alanlarındaki uzmanlar tarafından anlaşılması için bir algoritmanın mevcudiyetinin bir özelliği.

Asimptotik türleri ve gösterimi

Algoritmaların asimptotik analizinde, matematiksel asimptotik analiz notasyonunu kullanmak gelenekseldir. Bu durumda, algoritmaların karmaşıklığının aşağıdaki gibi gösterilen üç tahmini (asimptotik) dikkate alınır:

1) /(i) = O^(n))- karmaşıklık fonksiyonunun /(«) asimptotik olarak kesin tahmini veya algoritmanın operasyonel karmaşıklığı;
2) /(n) = 0(§(n)) - karmaşıklık fonksiyonunun asimptotik olarak kesin üst tahmini /( P);
3) /(l) = ?2(#(l)) - emek girdi fonksiyonunun asimptotik olarak tam alt tahmini /( P).

atama yerine C1^(n))çok sık olarak daha basit olan o(^(“)) “o” harfiyle küçük el yazısıyla kullanılır.

Formüllerin anlamlarını bir örnek kullanarak açıklayalım: / (n) = 0 (^2 (n)) yazılırsa, SONRA BU, fonksiyonun g(n)=og2 (n)/(«) karmaşıklık fonksiyonunun asimptotik olarak kesin bir tahminidir. Aslında, bir iddia şeklinde iki konumlu bir tanım vardır:

f(n) ise= @(log2(")),

ay g(n)\u003d günlük 2 (l) - f(n)'nin asimptotik olarak kesin tahmini.

Sabit faktörün algoritmanın karmaşıklık sırasını etkilemediğine dikkat edin, bu nedenle logaritmik karmaşıklık belirtilirken logaritmanın temeli atlanır ve bunlar basitçe f(l) = @(lо§(l)) yazılır, yani şu anlama gelir: logaritma birden büyük keyfi bir tabana sahiptir.

Asimptotiklerin resmi tanımları

Emek girdi fonksiyonunun asimptotik olarak kesin tahminiİle, İle 2 , l 0 , öyle ki l>l 0 için /(l) fonksiyonu, sabit çarpanlara kadar, fonksiyondan farklı değildir G( k), sonra fonksiyon g(n)/(k) fonksiyonunun asimptotik olarak kesin tahmini olarak adlandırılır.

3 s ] , s 2 e F, x ile > 0, ile 2 > 0:
- (3 l 0 e K, l 0 > 0: (/l e K, l > l 0:0 g(n) /(l) = 0(?(l))),

9^, N sırasıyla tüm gerçek ve doğal sayıların kümeleridir.

Karmaşıklık fonksiyonu için asimptotik olarak kesin üst sınır sözlü olarak şu şekilde tanımlanır: pozitif sayılar varsa İle ve l 0 , öyle ki l>l 0 için /(l) işlevi, işlevden daha hızlı büyümez g(n) sabit bir faktör c'ye kadar, sonra fonksiyon g(n) fonksiyon için asimptotik olarak tam üst sınır olarak adlandırılır. Ap).

Daha kesin bir resmi tanım şu şekildedir:

3 İle e %s > 0:
- (3 l 0 e X, l 0 > 0: (/l e K, l > l 0:0 s? #(l))) 0(g(n))

Karmaşıklık işlevi için asimptotik olarak kesin bir alt sınır sözlü olarak şu şekilde tanımlanır: pozitif sayılar varsa İle ve l 0 , öyle ki l>l 0 için /(l) işlevi, işlevden daha yavaş büyümez g(n) sabit bir faktöre kadar İle, o zaman fonksiyon?(k), fonksiyon için asimptotik olarak tam bir alt sınır olarak adlandırılır.

Daha kesin bir resmi tanım şu şekildedir:

3 İle 9^, İle > 0:
- (3 ben 0 e X, ben 0 > 0: (/i e K, ben > ben 0: 0 s? g(n)

/(Ben) = 0.^(n))

Aşağıdakilere dikkat et:

1) asimptotiklerin resmi tanımlarında belirtilen eşitsizlikler, genel durumda, bir değil, belirli bir dizi fonksiyonla, genellikle sayılamayan bir dizi terimle karşılanabilir, bu nedenle yapılar Q(g(n)), 0^(n)) ve 0.^(n)) sembolize etmek fonksiyon seti, emek girdisi /(i)'nin araştırılan fonksiyonunun karşılaştırıldığı; bu nedenle, /(n) = 0(?(n)), /(/0 = 0(? max (n)), Dn) = ?2(? m1n (n) formunun asimptotik gösteriminde )) "= » işareti yerine "e" işaretini kullanmak daha mantıklı olacaktır;
2) tasarımlar (g^(n)), 0^(n)) ve ?1^(n)), Belirli miktarlar için semboller olarak kullanıldığında, aşağıdaki gibi okunmalıdır: aynı olan, daha hızlı büyüyen ve daha yavaş olmayan herhangi bir fonksiyon g(n).

Asimptotiklerin tesadüfi ve farkı

Şu gerçeğe dikkat edelim: f(s) = 0(?(s)) tahmini, f(s) için hem üst hem de alt tahminler oluşturur, çünkü tanımı ilişkinin geçerliliğini varsayar. c g g(n)

Asimptotiklerin aşağıdaki özelliği oldukça açıktır: eğer tahmin φ(n) = ©^(n)) varsa, o zaman eşitlikler /( P) = 0(^(n)) ve /(n) = ?2(#(n)), yani. emek yoğunluğunun üst ve alt tahminleri birbiriyle örtüşür; if /(i) = 0(? max (i)) ve φ(n) = C1^ mn (n)), ve g maks (n)Фg m 1n(i), o zaman fonksiyon yok g(n),öyle ki /(i) = 0(?(i))).

Aşağıdaki durumlarda, emek yoğunluğunun üst ve alt tahminlerinin çakışması mümkündür:

1) giriş uzunluğunun tüm değerleri için karmaşıklık işlevi deterministik (rastgele olmayan) bir işlevdir, yani. gerçekleştirilen işlemlerin sayısı, ilk veri değerlerinin özelliklerine bağlı değildir; örneğin, lineer cebirsel denklem sistemlerini IS genişletme yöntemiyle çözmek için algoritmadaki bilinmeyen niceliklerin sayısına çarpma ve bölme işlemlerinin sayısının bağımlılık fonksiyonları;
2) emek yoğunluğu işlevi rastgele bir işlevdir, yani. gerçekleştirilen işlemlerin sayısı, ilk verilerin özelliklerine ve (veya) alınma sırasına bağlıdır ve minimum ve maksimum sayısını açıklayan / m | n (i), / max (i) işlevlerini belirleyebilirsiniz. algoritma yürütücüsü tarafından belirli bir giriş uzunluğu i için gerçekleştirilen işlemler, ancak bu işlevlerin her ikisi de aynı baskınlığa sahiptir, örneğin bunlar aynı sıradaki polinomlardır.

Operasyonel karmaşıklığın sırasını tahmin etmeye gelince akılda tutulması gereken üç önemli kural vardır:

1) karmaşıklık sırasını belirlemek için sabit faktörler önemli değildir, yani. 0 (k? g(n)) = 0(g(")) ;
2) eşitlik doğru olduğundan, iki fonksiyonun ürününün karmaşıklık sırası, karmaşıklıklarının ürününe eşittir:
0(gl(i) §2(i)) = 0 (?| (i)) 0 (#2(i)) ;
3) fonksiyonların toplamının karmaşıklık sırası, terimlerin baskın sırasına eşittir, örneğin: 0(i e + n 2 + n) = 0(i 5).

Yukarıdaki kurallar yalnızca bir asimptotik 0(") sembolünü kullanır, ancak bunlar tüm asimptotik tahminler için geçerlidir - ve 0( ) , ve &.{ ).

Temel işlevler kümesinde, bir işlevsel baskınlık listesi belirtebilirsiniz: bir değişken ise, a,b- sayısal sabitler varsa, aşağıdaki ifadeler doğrudur: i" i'ye hakimdir; i! hakimdir bir"; bir" Zj'ye hakim ise" a>b bir p hakim P b, eğer a> herhangi biri için 1 B e9? ; n bir hakim a>b log q(i)'ye hakim ise a > 1.

Ortalama emek yoğunluğunun tahmini

Uygulamada, yeniden Önemli olan hesaplamalar, M'nin karmaşıklığının matematiksel beklentisinin /(n) tahminidir, çünkü durumların büyük çoğunluğunda /(n) rastgele bir fonksiyondur. Bununla birlikte, rastgele /(n) ile algoritmaların deneysel çalışmaları sürecinde, ek bir sorun ortaya çıkar - güvenilir bir M tahmini için deneme sayısının seçimi. Bu sorunun üstesinden gelmek . Önerilen çözüm, /(n)'ye yaklaşmak için beta dağılımının kullanımına dayanmaktadır. Bu çok yapıcı ve çok yönlü bir tekniktir. Bununla birlikte, modern koşullarda, bilgisayar performansının oldukça yüksek olduğu durumlarda, çoğu durumda, mevcut değerlerin değişkenliğini izlemeye dayalı olarak, test kapsamını seçmek için daha basit bir yöntem kullanmak mümkündür. f(n) - tahminlerin varyansı belirtilen hatadan küçük olana kadar değerler tahmin edilir.

Bir Algoritmanın İşlemsel Karmaşıklığını Tahmin Etme

Bir algoritmanın karmaşıklığı, kontrol yapılarının analizine dayalı olarak belirlenebilir. Döngüleri ve özyinelemeli çağrıları olmayan algoritmaların sürekli karmaşıklığı vardır. Bu nedenle, bir algoritmanın karmaşıklığının tanımı, esas olarak döngülerin ve özyinelemeli çağrıların analizine indirgenir.

Silme algoritmasını düşünün İle boyut dizisinden -th öğesi P, dizinin öğelerini taşımaktan oluşan (+ 1) -th için P- dizinin başına bir pozisyon geri git ve eleman sayısını azalt P birim başına. Dizi işleme döngüsünün karmaşıklığı, Ah (p-k), döngü gövdesi (hareket işlemi) yürütüldüğünden bilgisayar kez ve döngü gövdesinin karmaşıklığı 0(1)'dir, yani. bir sabittir.

Söz konusu örnekte, karmaşıklık 0(") asimptotikleri ile karakterize edilir, çünkü bu algoritmada gerçekleştirilen işlemlerin sayısı veri değerlerinin özelliklerine bağlı değildir. Karmaşıklık işlevi deterministiktir ve her türlü asimptotik birbiriyle örtüşür: f(n) = Q(n-k), f(n) = 0(n-k) ve f(n) = Q(n-'den). Bu gerçek, tam olarak ©( ) işaretiyle kanıtlanmıştır. 0(*) ve/veya?2(*)'yi yalnızca bu asimptotikler farklıysa kullanın.

Döngü tipi (for, while, tekrar) karmaşıklığı etkilemez. Bir döngü diğerinin içine yerleştirilmişse ve her iki döngü de aynı değişkenin boyutuna bağlıysa, tüm yapı ikinci dereceden karmaşıklıkla karakterize edilir. Tekrarların iç içe geçmesi, karmaşıklığın büyümesinde önemli bir faktördür. Örnek olarak, bir dizi boyut için iyi bilinen arama ve sıralama algoritmalarının karmaşıklıklarını sunuyoruz. P:

sıralı aramada karşılaştırma işlemlerinin sayısı: 0(n);
ikili aramada karşılaştırma işlemi sayısı: 0(log 2 P);
basit değişim yöntemindeki karşılaştırma işlemlerinin sayısı (kabarcık sıralama): 0(n 2);
kabarcık sıralamasındaki permütasyon işlemlerinin sayısı: 0(n 2);

Basit değişim yöntemindeki karşılaştırma işlemlerinin sayısının asimptotik olduğuna dikkat edin. 0(n 2) ve permütasyon işlemlerinin sayısının iki farklı asimptotiği vardır 0(p 2) ve?2(0), çünkü karşılaştırma sayısı, sıralanan verilerin değerlerinin özgüllüğüne bağlı değildir, permütasyon sayısı ise bu özgüllük tarafından belirlenir. Permütasyonlar hiç gerçekleştirilemeyebilir - eğer veri dizisi başlangıçta doğru sıralanmışsa veya permütasyon sayısı maksimum olabilir - siparişin P 2 , - sıralanan dizi başlangıçta ters yönde sıralanmışsa.

Fonksiyon adı g(n) asimptotikte /(x) = @(x(x)) ve /(a) = 0(g(n)) karmaşıklık işlevi /(«) algoritmayı karakterize etmek için kullanılır. Böylece, polinom, üstel, logaritmik vb. karmaşıklık algoritmalarından söz edilir.