Algoritmanın karmaşıklığına bağlı olarak yaklaşık çalışma süresi. Algoritma karmaşıklığı işlevi türleri

Geleneksel olarak, bir algoritmanın karmaşıklık derecesini, kullandığı temel bilgisayar kaynaklarının miktarına göre değerlendirmek adettendir: işlemci süresi ve rasgele erişim belleği. Bu bağlamda, algoritmanın zaman karmaşıklığı ve algoritmanın hacim karmaşıklığı gibi kavramlar tanıtılmaktadır.

Zaman karmaşıklığı parametresi, program işletiminin etkileşimli bir modunu içeren görevler veya gerçek zamanlı kontrol görevleri için özellikle önemli hale gelir. Genellikle bazıları için bir kontrol programı yazan bir programcı teknik cihaz, hesaplamaların doğruluğu ile programın çalışma süresi arasında bir uzlaşma bulmalıyız. Kural olarak, doğruluktaki bir artış, sürenin artmasına neden olur.

Programın hacimsel karmaşıklığı, işlenmekte olan veri miktarı bilgisayarın RAM'inin sınırında olduğunda kritik hale gelir. Modern bilgisayarlarda hem RAM miktarındaki artış hem de katmanlı bir depolama sisteminin verimli kullanılması nedeniyle bu sorunun ciddiyeti azalır. Programın çok geniş, neredeyse sınırsız bir hafıza alanına erişimi var ( sanal bellek). Ana belleğin olmaması, yalnızca disk değişimlerinden dolayı bir miktar yavaşlamaya yol açar. Bu tür bir değiş tokuş sırasında zaman kaybını en aza indirecek teknikler kullanılır. Bu, önceden diskten ana belleğe aktarmanıza izin veren gerekli sayıda ileri hareket için program talimatlarının önbellek ve donanım görüntülemesinin kullanılmasıdır. istenen değerler. Yukarıdakilere dayanarak, kapasitif karmaşıklığı en aza indirmenin en önemli öncelik olmadığı sonucuna varabiliriz. Bu nedenle, aşağıda, esas olarak algoritmaların zaman karmaşıklığı ile ilgileneceğiz.

Program yürütme süresi, yürütülen işlemlerin sayısı ile orantılıdır. Tabii ki, boyutsal zaman birimleri (saniye) cinsinden, aynı zamanda işlemcinin hızına (saat frekansı) da bağlıdır. Algoritmanın zaman karmaşıklığının göstergesinin şuna göre değişmez olması için: özellikler bilgisayar, göreli birimlerle ölçülür. Tipik olarak, zaman karmaşıklığı, gerçekleştirilen işlemlerin sayısına göre tahmin edilir.

Kural olarak, algoritmanın zaman karmaşıklığı ilk verilere bağlıdır. Bu, hem ilk verilerin boyutuna hem de hacimlerine bağlı olabilir. Algoritmanın zaman karmaşıklığı parametresinin değerini Ta sembolüyle gösterirsek ve V harfi başlangıç ​​verilerini karakterize eden bazı sayısal parametreleri belirtirse, zaman karmaşıklığı bir Ta(V) fonksiyonu olarak temsil edilebilir. V parametresinin seçimi, çözülmekte olan probleme veya bu problemi çözmek için kullanılan algoritmanın tipine bağlıdır.

Örnek 1. Pozitif bir tamsayının faktöriyelini hesaplamak için algoritmanın zaman karmaşıklığını tahmin edelim.

Fonksiyon Faktöriyel(x:Tamsayı): Tamsayı;

var m, ben: Tamsayı;

i:=2 için x Do m:=ro*i;

Program tarafından gerçekleştirilen toplam işlem sayısını hesaplayalım. verilen değer X. m:=1; ifadesi bir kez yürütülür; döngü gövdesi (iki işlemin olduğu: çarpma ve atama) x - 1 kez yürütülür; atama bir kez yapılır Faktöriyel:=m. İşlemlerin her biri bir karmaşıklık birimi olarak alınırsa, tüm algoritmanın zaman karmaşıklığı 1 + 2 (x - 1) + 1 = 2x olacaktır. Buradan, x değerinin parametre olarak alınması gerektiği açıktır. . Zaman karmaşıklığı fonksiyonunun aşağıdaki gibi olduğu ortaya çıktı:

Bu durumda, zaman karmaşıklığının lineer olarak data parametresine - faktöriyel fonksiyonun argümanının değerine - bağlı olduğunu söyleyebiliriz.

Örnek 2. İki A = (a1, a2, ..., ak), B = (b1, b2, ..., bk) vektörünün skaler çarpımının hesaplanması.

i:=l için k yapmak AB:=AB+A[i]*B[i];

Bu problemde girdi verisinin boyutu n = 2k'dir. Gerçekleştirilen işlem sayısı 1 + 3k = 1 + 3(n/2). Burada V= k= n/2 alabiliriz. Algoritmanın karmaşıklığının A ve B vektörlerinin öğelerinin değerlerine bağımlılığı yoktur. Önceki örnekte olduğu gibi, burada zaman karmaşıklığının data parametresine doğrusal bağımlılığı hakkında konuşabiliriz.

İki teorik problem genellikle bir algoritmanın zaman karmaşıklığı parametresiyle ilişkilendirilir. İlki şu soruya bir cevap bulmayı içerir: Problemi çözmek için algoritma geliştirilerek zaman karmaşıklığı değerinin hangi sınırına ulaşılabilir? Bu sınır görevin kendisine bağlıdır ve bu nedenle görevin kendi özelliğidir.

İkinci problem, algoritmaların zaman karmaşıklığına göre sınıflandırılmasıyla ilgilidir. Tα(V) fonksiyonu genellikle V ile büyür. Ne kadar hızlı büyür? Ta'nın V'ye doğrusal bağımlılığı olan (düşündüğümüz örneklerde olduğu gibi), ikinci dereceden bağımlı ve daha yüksek dereceli bağımlı algoritmalar vardır. Bu tür algoritmalara polinom denir. Ve karmaşıklığı herhangi bir polinomdan daha hızlı büyüyen algoritmalar vardır. Teorisyenler - algoritma araştırmacıları tarafından sıklıkla çözülen problem şu sorudur: belirli bir problem için bir polinom algoritması mümkün mü?

Algoritmaların analizinde sıklıkla karşılaşılan fonksiyonlar:

• kayıt N(logaritmik zaman),
• N(doğrusal zaman),
• N kayıt N,
• N 2 (kare zaman),
• 2N(üstel zaman).

İlk dört fonksiyon düşük büyüme hızına sahiptir ve çalışma süresi bu fonksiyonlar tarafından tahmin edilen algoritmalar hızlı sayılabilir. Üstel bir fonksiyonun büyüme oranı bazen "patlayıcı" olarak nitelendirilir. Karşılaştırma için, karmaşıklığı (işlem sayısı) bu işlevler tarafından doğru bir şekilde yansıtılan algoritmalar olduğunu varsayalım. Saniyede 10 12 işlem hızında çalışan bir bilgisayarda bu algoritmaları çalıştıralım. giriş uzunluğu ile N≤ 100000, performansı ilk dört fonksiyon tarafından tahmin edilen algoritmalar, saniyenin çok küçük bir kısmında bir yanıt alacaktır. Karmaşıklık 2'ye sahip bir algoritma için Nçalışma süresi aşağıdaki gibi tahmin edilmektedir:

• N= 50 ≈ 19 dakika,
• n= 60 ≈ 320 saat,
• n= 70 ≈ 37 yaşında.

Soru 15=49. Ardışık, döngüsel ve yinelemeli algoritmalar.

Sıralı Algoritmalar - blokların belirli bir şema sırasına göre birbiri ardına sırayla yürütüldüğü algoritmalar.

Örnek. Kenarları a,b,c olan bir üçgenin çevresini hesaplayın.13

Dallanma Yapısı Algoritması

Uygulamada, bir problemin çözümünü bir algoritma biçiminde temsil etmek nadiren mümkündür.

doğrusal yapı. Genellikle bazı orta seviyelere bağlı olarak

hesaplama sonuçları biri veya diğeri üzerinde gerçekleştirilir

formüller, yani bazılarının performansına bağlı olarak boole koşulu

hesaplama işlemi bir veya başka bir formüle göre gerçekleştirilir.

Böyle bir hesaplama işleminin algoritmasına algoritma denir.

dallanma yapısı.

Dallanma, yalnızca yürütmeyi organize eden bir kontrol yapısıdır.

adalete bağlı olarak belirtilen iki eylemden biri

bazı durum.

Koşul, iki olası yanıtı olan bir sorudur: evet veya hayır.

Dallanma iki biçimde kaydedilir: tam ve eksik (Şekil 1 a, b).

a) tam form b) eksik form

döngüsel algoritmalar – için aynı matematiksel bağımlılıklara (blok diyagramlar) göre değerleri tekrar tekrar hesaplamanın gerekli olduğu algoritmalar Farklı anlamlar içerdikleri miktarlar. Döngülerin kullanılması, devrenin hacmini önemli ölçüde azaltabilir

Algoritma ve karşılık gelen programın uzunluğu. ile döngüler var

verilen ve bilinmeyen tekrar sayısı. Belirli sayıda tekrarla -

sayaç ile döngü. Bilinmeyen sayıda tekrarla - önkoşullu bir döngü,

son koşullu döngü.

Doğrudan veya dolaylı olarak kendisine atıfta bulunan bir işleve (veya prosedüre) özyinelemeli denir. Özyineleme, bir işlevi önceki ve daha önce tanımlanmış değerleri aracılığıyla tanımlamanın yanı sıra bir yol yöntemidir.

işlevin kendisini farklı bir bağımsız değişkenle çağırdığı hesaplamaların organizasyonu

Yinelemeli algoritmaları uygularken, her yineleme adımı soruna doğrudan bir çözüm sağlamaz, aynı soruna indirger. daha küçük. Bu süreç öyle büyük bir göreve yol açmalıdır ki,

çözüm oldukça kolaydır. Ayrıca, "ters hareket", artan boyut sorunu için ilkine kadar ardışık çözümler sunar. Yinelemeli bir yordamın uygulanması, henüz işini tamamlamadığı yordama yapılan tüm çağrılarda yer alan verileri depolayan bir yığına (depo tipi bellek) dayanır. Yineleme, algoritma kendisine atıfta bulunduğunda hesaplama sürecini düzenlemenin bir yoludur. Özyineleme ilkesi çözmemizi sağlar zor görev daha basit alt problemleri sırayla çözerek Kural olarak, çok fazla seçeneği gözden geçirmeniz gereken durumlarda yineleme gereklidir. Özyineleme çeşitlerinden biri olarak kabul edilir döngüsel algoritma. Özyinelemeli organizasyon biçimi, algoritmaya daha kompakt bir biçim vermeyi mümkün kılar. Böylece, problem karmaşıktan basite çözülür - özyinelemeli algoritmanın içeriği, aynı türden daha basit bir nesne aracılığıyla daha karmaşık bir nesneyi yansıtır. Tipik olarak, özyinelemeli bir algoritma aşağıdaki ana bölümleri içerir:

– döngüyü sonlandırmak için koşul;

- amaçlanan eylemleri içeren özyinelemenin gövdesi

her yinelemede yürütme;

yinelemeli algoritmanın kendisini çağırdığı yineleme adımıdır.

Doğrudan ve dolaylı özyinelemeyi ayırt edin. İlk durumda, algoritma

kendini çağıran bir işlev içerir. Bir işlev başka bir işlevi çağırırsa, o da ilkini çağırırsa, o işlev

dolaylı özyinelemeli denir.

Özyinelemeli algoritmalar için temel gereklilik, tersine çevirme işleminin olmamasıdır.

sonsuz olmalıdır. Başka bir deyişle, uygulanması gerekir.

çağrı tamamlama için kontrol veya özyinelemeli bir tanımda olmalıdır

daha fazla başlatmanın altında olduğu bir kısıtlama var

tekrarlama sonlandırılır.

Özyinelemeli bir fonksiyon örneği, bir sayının faktöriyelini hesaplamaktır.

int factoria(int n)

eğer (n) n* factoria(n-1) döndürürse;

aksi takdirde 1 döndürür;

Özyinelemeli bir prosedür örneği:

prosedür Rec(a: tamsayı); a>0 ise başla, sonra Rec(a-1); yaz(a); son;

Ana programa, örneğin Rec(3) biçiminde bir çağrı koyarsak ne olacağını düşünelim. Aşağıda, ifadelerin yürütüldüğü sırayı gösteren bir akış şeması bulunmaktadır.

Algoritmanın etkinliğini değerlendirmek için en önemli göstergeler şunlardır:

Algoritma yürütme süresi,
- gerekli miktarda RAM.

Günümüzde, yarım asırlık teknolojik ilerleme nedeniyle, ilk gösterge (yürütme süresi) genellikle ikinciden çok daha önemlidir, bu nedenle sadece daha ayrıntılı olarak ona odaklanacağız.

Algoritmaların Yürütme Süresini Tahmin Etmeye Yönelik Basitleştirmeler

D. Knuth'un çalışmalarında, algoritmaların yürütme süresinin analizi için aşağıdaki yaklaşım önerilmiştir: toplam süre, her temel işlem için maliyet * frekansın toplamıdır. Temel işlemler arasında toplama, çarpma, bölme, bir diziden dizine göre öğe alma, tamsayıları karşılaştırma vb. yer alabilir. Bu durumda, algoritmanın yürütme süresinin bir tahmininin hesaplanmasının oldukça sıkıcı olduğunu görmek kolaydır. Bu nedenle, A. Turing, algoritma yürütme süresi tahminlerinin kaba tahminlerini bile kullanmanın uygun olduğunu söyledi: algoritmanın çalışması sırasında meydana gelme sıklıklarına bağlı olarak çeşitli işlemlere ağırlıklar atayabilir ve yalnızca karşılık gelen işlemleri hesaba katabilirsiniz. en büyük ağırlıklar Örneğin matrisleri çarparken sadece çarpma ve sayı yazma gibi işlemler dikkate alınmalıdır çünkü bunlar en yaygın işlemlerdir.Sadece en çok dikkate alındığındaortak işlemler - ilk sadeleştirme, algoritmaların yürütme süresinin yaklaşık olarak hesaplanması için önerilmiştir.

İkinci basitleştirme, algoritmanın yürütme süresinin nihai tahminine çok az katkıda bulunan daha düşük dereceli terimlerin (yani terimler) atılmasıdır. Örneğin (bundan sonra, N sayısı giriş verilerinin boyutunu karakterize eder),

\(1/6 N^3 + 20N + 16 \sim 1/6N^3\),

\(1/6N^3\) yerine "bu algoritmanın karmaşıklığı var \(O(N^3)\", \(3N^4\) yerine "bu algoritmanın karmaşıklığı var \(O(N) ^4)\ )".

O-big'un tanımı

Tüm \(x\) için öyle bir \(C>0\) sabiti varsa, \(f\)'nin \(x \to x_0\) için \(g\)'nin "O'dan büyük" olduğunu söylüyoruz. noktasının komşuluğundan \(x_0\) eşitsizliği \(|f(x)| \leq C|g(x)|\) tutar. Aşağıda tanımın bir gösterimi bulunmaktadır (\(x\) ekseni giriş verilerinin boyutudur, \(y\) ekseni algoritmanın yürütme süresidir). Belirli bir noktadan itibaren girdi boyutunun \(\propto\) \(f(n)\)'ye yönelmesinden dolayı \(g(n)\)'den daha yavaş büyüdüğünü ve genel olarak \(g( n)\) yukarıdan sınırlandırıyormuş gibi.

Örnekler. \(1 = O(N), N = O(N^2).\)

\(O(N)\) biçimindeki tahminlerle birlikte, \(\Omega(N)\) (omega büyük) tahmini kullanılır. Fonksiyonun büyümesi için daha düşük bir tahmin anlamına gelir. Örneğin, \(f(N)=\Omega(N^2)\) işlevinin algoritma işlemlerinin sayısını tanımlamasına izin verin. Bu, en iyi durumda bile en az \(N^2\) eylemin gerçekleştirileceği anlamına gelir. \(O(N^3)\) tahmini, en kötü durumda \(N^3\) eylemlerin sırasından fazlasının olmayacağını garanti ederken. Üst ve alt asimptotik sınır olan \(\Teta(N)\) (teta) sınırı da kullanılır.\(Üst ve \(\Omega(N)\) eşleşir.Dolayısıyla, \(O(N)\), algoritmanın en kötü girdi verileri üzerindeki yaklaşık bir tahminidir,\(\Omega(N)\) - en iyi girişte,\(\Theta(N)\) aynının kısaltmasıdır\(O(N)\) ve \(\Omega(N)\).

Farklı algoritmalar için çalışma zamanı tahminleri

Belirtin T(N) - algoritmanın yürütme süresi. Çalışılan algoritma şu şekilde olsun:

1. Sadece dahil olmak üzere talimat seti temel işlemler:

Açıklama 1;
...
ifade k;

O zaman T(N) = T(ifade 1) + ... + T(ifade k).

Çünkü her talimat yalnızca temel işlemleri içerir, bu durumda bu kod parçasının yürütme süresi giriş verilerinin boyutuna bağlı değildir (giriş verilerinin boyutuyla birlikte büyümez), yani. bir sabittir. Bu algoritma O(1) karmaşıklığına sahiptir.

2.if-else ifadeleri

Eğer (koşul) (
ifade dizisi 1
}
başka(
ifade dizisi 2
}

Burada, 1. ifade dizisi veya 2. ifade dizisi yürütülecektir, bu nedenle, çünkü yürütme süresinin en kötü durum tahminini elde etmek istiyoruz, T(N) = max(T(ifade dizisi 1), T(ifade dizisi 2)). Örneğin, 1. ifade dizisinin yürütme zamanı O(N) ve deyim dizisi O(1) ise, o zaman T(N) = O(N).

için (i = 0; ben< N; i++) {
ifade dizisi
}

Çünkü döngü N kez yürütülür, ardından ifade dizisi de N kez yürütülür. T(ifade dizisi) = O(1) ise, T(N) = O(N)*O(1) = O(N).

4. İç içe döngüler.

için (i = 0; ben< N; i++) {
için (j = 0; j< M; j ++){
...
}
}

Dış döngü N kez yürütülür. Dış döngü her yürütüldüğünde, iç döngü M yürütülür.

Şimdi bu kodu göz önünde bulundurun:

için (i = 0; ben< N; i++) {
için (j = ben + 1; j< N; j ++){
ifade dizisi
}
}

Dış döngünün yinelemesine bağlı olarak iç döngünün yineleme sayısındaki değişime bakalım.

I döngüsü j (yürütme sayısı)
0 N
1N-1
2 N-2
...
N-1 1

Daha sonra ifade dizisi N + N-1 + ... + 1 kez yürütülecektir. Bu tür miktarların hızlı bir şekilde hesaplanması için, matematiksel analizden elde edilen formüller yararlıdır, bu durumda formül

Onlar. bu algoritma \(O(N^2)\) karmaşıklığına sahip olacaktır.

Ve işte bu tür durumlar için yararlı olan ve en sık ihtiyaç duyulan diğer formüller:

4. Bir iddia bir yöntem çağrısı içerdiğinde, iddianın zaman tahmini, yöntemin zaman tahmininden hesaplanır. Örneğin:

için (j = 0; j< N; j ++){

Yöntemin yürütme zamanı \(g(N)=O(N)\) ise, bu durumda \(T(N) = O(N)*O(N) = O(N^2)\).

5. İkili (ikili) arama.

int l = 0;
int u = A.uzunluk - 1
intm;
iken (l<= u) {
m = l + (u - 1)/2
eğer A[m]< k {
l = m+1;
}
aksi takdirde A[m] == k (
dönüş m;
}
başka(
u = m - 1;
}
}
-1 döndürür;

İkili arama, sıralanan dizideki k sayısının dizinini bulmanızı sağlar, eğer bu sayı içinde değilse, o zaman -1 döndürülür. Önce k'yi dizinin ortasındaki sayı ile karşılaştırırız. Eğer k bu sayıdan küçükse, onu dizinin sol yarısında, daha fazlaysa sağ yarısında aramalıyız. Ardından k, önceki adımda seçilen dizinin yarısının ortasındaki sayı ile karşılaştırılır ve bu böyle devam eder. Her iterasyonda arama uzayı yarıya iner. Şu soru ortaya çıkıyor: en kötü durumda (yani, dizide k'ye eşit bir sayı bulunmadığında ve karşılaştırma için veri kalmadığında) kaç yineleme yapılması gerekecek?

Görüyoruz ki, 1. iterasyondan sonra \(N/2\) indeksi aranacak \(k\) verisi olacak, 2. iterasyondan sonra \(N/4\) data olacak, 3. iterasyondan sonra - \(N /8\) vb. \(\frac(N)(2^x)=1\) denklemini çözersek, en kötü durumdaki iterasyon sayısını buluruz. Bu denklem \(2^x=N\) denklemine eşdeğerdir, dolayısıyla \(x=log_(2)(N)\) veya \(x=log(N)\) (logaritmanın tanımına bakın) . Bu nedenle, ikili arama algoritmasının karmaşıklığının tahmini \(O(logN)\).

İyi haber şu ki, çoğu algoritmanın yürütme süresini karakterize etmek için yalnızca birkaç işlev yeterlidir: \(1, logN, N, NlogN, N^2, N^3, 2^N\). Grafik, girdi verilerinin boyutuna bağlı olarak algoritma yürütme süresinin farklı büyüme oranlarını göstermektedir:

Bu grafikten, özellikle, algoritmanın yürütme süresinin "logaritmik", yani algoritmanın \(O(logN)\) karmaşıklığı var, o zaman bu çok güzel, çünkü yürütme süresi, girdi verilerinin boyutundaki artışla çok yavaş büyür, yürütme süresi doğrusal olarak girdi verilerinin boyutuna bağlıysa, bu da fena değildir, ancak üstel çalışma süresine sahip algoritmalar kullanmamak daha iyidir (\(O(2^N)\)) hiç veya yalnızca çok küçük verilerde kullanın.

P ve NP sınıfları

Argümanın pozitif tamsayı değerleri için tanımlanan gerçek bir negatif olmayan fonksiyon \(f(m)\), gerçek katsayılara sahip bir polinom \(P(m)\) varsa, polinomla sınırlı olarak adlandırılır, öyle ki \(f( m) \leq P( m)\) tüm \(m \in N^+\) için. "Polinom" çalışma süresine sahip algoritmaların bulunduğu problemler, P sınıfına aittir (bu problemler genellikle hızlı ve sorunsuz bir şekilde çözülür).

Resmi tanımlama. Bir L dili, ancak ve ancak aşağıdaki gibi deterministik bir Turing makinesi M varsa P sınıfına aittir:

Herhangi bir girdi verildiğinde, M işini polinom zamanında tamamlar,
- tüm \(x \in L\) için M sonucu 1 verir,
- \(L\'ye ait olmayan tüm \(x\) için M, 0 sonucunu döndürür.

NP sınıfının sorunları- koşulu karşılayan problemler: eğer bir cevap varsa (olası çözüm), o zaman doğrulamak kolaydır - bunun bir çözüm olup olmadığını kontrol etmek.

NP sınıfından bir problem örneği düşünün. Bir dizi tam sayı verilsin, örneğin (-7, -3, -2, 5, 8). Bu sayılar arasında toplamı 0 olan 3 sayı olup olmadığının öğrenilmesi gerekir. Bu durumda cevap "evet" olur (örneğin, böyle bir üçlü (-3, -2.5) sayılarıdır). tam sayı kümelerinin boyutu artar, 3 elemandan oluşan alt kümelerin sayısı katlanarak artar. Bu arada, bize böyle bir alt küme verilirse (buna sertifika da denir), o zaman elemanlarının toplamının olup olmadığını kolayca kontrol edebiliriz. 0'a eşittir.

Resmi tanımlama:

Bir L dili, ancak ve ancak \(p\) ve \(q\) polinomları ve aşağıdaki gibi deterministik bir Turing makinesi M varsa NP sınıfına aittir:

Herhangi bir \(x,y\) için \((x,y)\) girişindeki M makinesi \(p(|x|)\) zamanında çalışır,
- herhangi bir \(x \in L\) için, \(M(x,y)=1\) olacak şekilde \(q(|x|)\) uzunluğunda bir \(y\) dizisi vardır,
- \(L\)'den olmayan herhangi bir \(x\) ve \(q(|x|)\) \(M(x,y)=0\) uzunluğundaki tüm diziler için.

polinom indirgenebilirliği veya Karp indirgenebilirliği. Herhangi bir \(x\) \(f_(1)(x)=f_( için bir \(f \in P\) işlevi varsa, \(f_1\) işlevi \(f_2\) işlevine indirgenir 2 )(f(x))\).

Sorun T denir NP-tamamlandı NP sınıfına aitse ve NP'den gelen herhangi bir problem polinom zamanında ona indirgenir. NP-tam probleminin belki de en iyi bilinen örneği SAT (tatmin edilebilirlik) problemidir. Boole değişkenleri, "AND", "OR", "NOT" operatörleri ve parantezler içeren bir formül verilsin. Sorun şudur: Bir formülde yer alan tüm değişkenlere değer atamak mümkün müdür? yalan Ve doğru Böylece formül " değerini alır. doğru".

Sorun T denir NP-sert, polinom zamanında T'ye indirgenen bir NP-tam problemi varsa. Burada Cooke indirgenebilirliğini kastediyoruz. Cook'a göre \(R_1\) probleminin \(R_2\)'ye indirgenmesi, sorunun çözümünü bulan fonksiyonun \(R_2\) olması şartıyla \(R_1\) problemini çözen bir polinom-zaman algoritmasıdır. ona bir kehanet olarak verilir, yani ona ulaşmak sadece bir adım sürer.

İşte yukarıdaki problem sınıfları arasındaki olası ilişkiler (bilim adamları hala P ve NP'nin aynı olup olmadığından emin değiller).

Elbette, herhangi bir algoritmayla ilgili olarak O (log n) gibi notasyonlara veya "logaritmik hesaplama karmaşıklığı" gibi ifadeler duymuşsunuzdur. Ve bunun ne anlama geldiğini hala anlamadıysanız, bu makale tam size göre.

Zorluk derecesi

Algoritmaların karmaşıklığı genellikle yürütme süresi veya kullanılan bellek ile tahmin edilir. Her iki durumda da, karmaşıklık girdi verilerinin boyutuna bağlıdır: 100 öğelik bir dizi, 1000 öğelik benzer bir diziden daha hızlı işlenir. Aynı zamanda, çok az kişi tam zamanı önemser: işlemciye bağlıdır, veri türü, programlama dili ve diğer birçok parametre. Yalnızca asimptotik karmaşıklık önemlidir, yani girdinin boyutu sonsuza gitme eğiliminde olduğundan karmaşıklık.

Diyelim ki bazı algoritmaların n girdi veri öğesini işlemek için 4n 3 + 7n koşullu işlemleri yürütmesi gerekiyor. n arttıkça, toplam çalışma süresi, n'yi kübe yükseltmek, 4 ile çarpmak veya 7n eklemekten önemli ölçüde daha fazla etkilenecektir. Daha sonra, bu algoritmanın zaman karmaşıklığının O(n 3)'e eşit olduğunu, yani kübik olarak girdi verilerinin boyutuna bağlı olduğunu söylüyoruz.

Büyük O'nun kullanımı (veya sözde O notasyonu), fonksiyonların asimptotik davranışını karşılaştırmak için kullanıldığı matematikten gelir. Resmi olarak, O(f(n)) algoritmanın çalışma süresinin (veya kullanılan bellek miktarının), girdi verilerinin miktarına bağlı olarak bazı sabitlerin f(n) ile çarpılmasından daha hızlı olmadığı anlamına gelir.

örnekler

O(n) - doğrusal karmaşıklık

Bu tür bir karmaşıklık, örneğin, sıralanmamış bir dizideki en büyük öğeyi bulma algoritmasına sahiptir. Hangisinin en büyük olduğunu bulmak için dizinin tüm n öğelerini gözden geçirmeliyiz.

O(log n) - günlük karmaşıklığı

En basit örnek ikili aramadır. Dizi sıralanmışsa, ikiye bölerek belirli bir değer içerip içermediğini kontrol edebiliriz. Ortadaki öğeyi kontrol edelim, eğer istenenden büyükse, dizinin ikinci yarısını atacağız - kesinlikle orada değil. Daha azsa, tam tersi - ilk yarıyı atarız. Ve böylece ikiye bölmeye devam edeceğiz, sonuç olarak log n elemanlarını kontrol edeceğiz.

O(n 2) - ikinci dereceden karmaşıklık

Bu karmaşıklık, örneğin, ekleme sıralama algoritmasına sahiptir. Kanonik uygulamada, iç içe geçmiş iki döngüden oluşur: biri tüm dizinin içinden geçmek için, ikincisi zaten sıralanmış kısımda bir sonraki öğe için bir yer bulmak için. Bu nedenle, işlem sayısı dizinin boyutuna n * n, yani n 2 olarak bağlı olacaktır.

Başka zorluk dereceleri de var ama hepsi aynı prensibe dayanıyor.

Algoritmanın çalışma süresinin girdi verilerinin boyutuna hiç bağlı olmadığı da olur. Daha sonra karmaşıklık O(1) olarak gösterilir. Örneğin, bir dizinin üçüncü öğesinin değerini belirlemek için öğeleri hatırlamanız veya üzerinde birkaç kez yinelemeniz gerekmez. Her zaman giriş veri akışındaki üçüncü öğeyi beklemeniz yeterlidir ve bu, herhangi bir miktarda veri için hesaplanması aynı süreyi alan sonuç olacaktır.

Benzer şekilde, değerlendirme önemli olduğunda bellekten yapılır. Ancak, girdi boyutu diğerlerine göre arttığında, ancak yine de daha hızlı çalıştığında algoritmalar önemli ölçüde daha fazla bellek kullanabilir. Ve tam tersi. Bu, mevcut koşullara ve gereksinimlere dayalı olarak sorunları çözmenin en iyi yollarını seçmeye yardımcı olur.

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), algoritmanın adımlarla ölçülen yürütme süresidir (sonucu elde etmek 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; ara, geri dön).

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

https://pandia.ru/text/78/183/images/image002_151.gif" genişlik="178 yükseklik=60" yükseklik="60">

Olay T(N)= C* N2 kare matris için geçerlidir.

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

Orijinal matris özdeşlik ise, En İyi Durumu elde ederiz.

Matristeki elemanların yarısı 0, yarısı 1 ise Ortalama Durumu elde ederiz.

Devamlı İLE tam olarak ifade edilemeyen, dış faktörlerin algoritmaların yürütme süresi (bilgisayar hızı, derleme hızı) üzerindeki etkisini 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 Ω gösterimlerdir.

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

Asimptotik karmaşıklığın büyüme oranını tanımlamak için, O gösterimi. 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=sabit (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ığının bir büyüme sırası vardır T(N)= Ö(N2 ).

Gösterilebilir ki, herkes 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 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 birden fazla karmaşıklığı varsa 3 N, o zaman hızın büyüme sırasının katı olamayacağı gösterilebilir. Ö(2 N):

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

Sabitler olsun C, N0 , öyle ki aşağıdaki eşitsizlik geçerli olur:

3N £ C*2 N, N > N0 .

Buradan şunu elde ederiz:

İLE³ (3/2)2, N > N0 .

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

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

T(N) ³ W(F(N))

Eşitsizlik (2), bazı sabitlerin olduğunu ima eder. İLE, hangisi için N® ¥ zaman karmaşıklığı

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

İlk verilerin boyutuna bağlı olarak T(N)'yi (asimptotik zaman karmaşıklığı) doğru bir şekilde belirlemenin zorluğu göz önüne alındığında, pratikte, algoritmanın zaman karmaşıklığının 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 yazalım:

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

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

Eğer C1» 0 (С1=0.00001), sonra eşitsizlik

10-5 N2 > 3 N2 –100 N+6, N³ 1

yapılmaz.

Ama gösterilebilir ki artan karmaşıklık sırası

3n2 -100n+6¹ AÇIK).

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 yapılmaz.

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.

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">

N!

Ö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 ile karakterize edilen küçük bir karmaşıklık büyümesine kıyasla C2.

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

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

A1: 100 N

A2: 100 N* günlükN

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 ederken önemli ölçüde daha düşük oranlar verecektir.

-de N=10 ¸ 58 A3 tercih edilir.

-de N=59 ¸ 1024 A2 en verimli olacaktır.

-de 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 algoritmadan (Р1 ve Р2) oluşmasına izin verin. Ö(F(N)) Ve Ö(G(N)) sırasıyla. Ardından, 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 iki paralel çalışan algoritmadan oluşan bir programın zaman karmaşıklığı Ö(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.

Yinelemeli algoritmaların karmaşıklığının, algoritmik yapıların iç içe geçmiş olması nedeniyle tahmin edilmesi kolay değildir.

F(N) Þ F(N* F(N-1))

Örneğ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 yinelemeli algoritmalar genellikle zaman karmaşıklığına sahiptir T(N) ~ Ö(BİR) , Nerede A= sabit, bu da aynı sorunu çözmek için özyinelemeli olmayan bir algoritmanın karmaşıklığından daha büyük bir toplam karmaşıklığa neden olur.

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ı bilinmez 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ığına analitik bir bağımlılık oluşturmak için işlevi değerlendirin T(N) bazı aralıklarla [ Nmin, Nmaks] . Daha sonra, bazı analitik fonksiyonların bulunan eğrisine, fonksiyonun parametrelerindeki bir değişiklik ve yaklaşım hatasının bir tahmini ile yaklaşılır.

Kural olarak, iyi bilinen zaman karmaşıklığı fonksiyonları böyle bir fonksiyon olarak kullanılır: Ö(N!), Ö(XN), Ö(NX), Ö(günlükN), Ö(https://pandia.ru/text/78/183/images/image010_72.gif" width="307" height="225 src=">Program üzerinde yapılan deney sonucunda zaman karmaşıklığı tablosu elde edilmiştir. Elde edilen:

Fonksiyonun bir yaklaşımının araştırılması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:

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

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

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

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

Bir algoritmanın çalışma süresi, yani zaman karmaşıklığı, bir dereceye kadar bir polinom ile yukarıdan sınırlandırılmışsa, 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 : Doğrusal karmaşıklığa sahip problemlerin P'ye dahil olduğu gösterilebilir.

T(N)= Ö(N1 )

Deterministik olmayan bir algoritma kullanılarak polinom zamanında çözülebilen bir NP problemleri sınıfını tanıtalım.

Algoritmanın durumunu yürütülebilir dosyanın bir dizi adresi olarak tanımlayalım. şu an süreç durum vektörüne eşdeğer olan tüm değişkenlerin komutları ve değerleri. Bu nedenle, çoğu algoritma deterministiktir, yani herhangi bir durum için, içlerinde kabul edilebilir yalnızca bir 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.

İÇİNDE deterministik olmayan algoritma (NDA) herhangi bir durum için, birden fazla geçerli sonraki durum olabilir, yani böyle bir algoritma herhangi bir zamanda birden fazla ifade yürütebilir.

NDA rastgele veya olasılıksal 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:

Deterministik bir algoritma (DA) bu sorunu sırayla çözecektir (tüm seçeneklerin sıralanması, A0 alternatifini seçene kadar K0 optimallik kriteri ile karşılaştırma).

NDA aynı anda (paralel olarak) tüm alternatifleri alabilir ve kendisini formda kopyalayarak K0 ile karşılaştırabilir. ayrı süreç bağımsız çalışan her alternatif için.

Bu durumda, herhangi bir kopya hatalı bir sonuç alındığını veya sonucun alınmadığını tespit ederse yürütmesini durdurur. Kopya, K0'ı tatmin eden bir çözüm bulursa, başarı ilan eder ve diğer tüm kopyalar çalışmayı durdurur.

O. NDA üç parametre ile karakterize edilir:

1. seçenek değerleri S kümesinin öğeleri olan çok değerli bir işlevdir;

2. arıza algoritmanın kopyasının çalışmasının durması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çbiri fiziksel cihaz sınırsız deterministik olmayan davranış yeteneğine 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 NP'deki herhangi bir problem kadar zorsa, NP-zordur.

NP'ye ait bir NP-zor problemi denir NP-tam dolu görev. Bu tür problemler, NP'deki herhangi bir problemden daha az zor değildir. Ayrıca, bir NP-hard veya NP-complete problemi için bir PDA'nın varlığı, P ve NP sınıflarının çakıştığı, yani 3. sınıftaki tüm problemlerin 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, NP'deki problemleri çözmek için başka bir PDA elde etmek için kullanılabileceğini göstermek gerekir.

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

Bir problemi çözmek için bir algoritmayı diğerini çözmek için bir algoritma elde etmek için kullanma fikri, algoritma teorisindeki en önemli konulardan biridir.

tanım 1: Görev P1, varsa görev P2'ye dönüştürülür özel durum P1 problemi, polinom zamanında P2 probleminin bazı özel durumlarına dönüştürülebilir. Daha sonra P1 çözümü, P2 probleminin belirli bir durumunun çözümünden polinom zamanda elde edilebilir.

https://pandia.ru/text/78/183/images/image024_39.gif" genişlik="158 yükseklik=56" yükseklik="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ı

başka başarısız

P1 probleminin P2'ye dönüştürülmesi kullanılarak, tatmin edilebilirlik probleminin sınırlı durumunun bile NP-tamamlandığı gösterilebilir.

K-fizibilite .

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

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

e* (X1 , X2 ,…, xn) ® e* (xi)

Bunu yapmak için, ayrık sırasını azaltma yöntemini kullanırız.

(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*, fizibiliteyi kanıtlamak orijinal fonksiyon e.

Özel durum: K=2'de fonksiyon e R'ye dahil

NP-sınıfı problem örnekleri aynı zamanda grafiklerdeki görevler :

1) Yönsüz bir grafiğin maksimum kliklerinin belirlenmesi (NP-zor problem).

2) Tam bir alt çizge belirleme sorunu (NP-tamamlama sorunu).

3) Yönsüz bir grafik için (NP-tamamlama problemi) kardinalite L'nin tepe örtüsünün belirlenmesi.

4) Yönsüz bir çizgenin (NP-zor problemi) maksimum köşe örtülerinin belirlenmesi.

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

6) Gezici satıcı problemi: her tepe noktasında tek bir oluşumla bir grafik boyunca optimal hareketin belirlenmesi (NP-zor problem).

7) Çizelgeleme problemi (NP-tamamlama problemi).

2.6 Algoritmik olarak çözülemeyen problemler

Paylaşma sorunları Bekar Ve cüsseli.

Örneğin:

5+7=? tek sorundur.

x+y=? kitlesel bir sorundur.

Paradoksal olan nesneleri elde etmek veya paradoksal nesnelerin varlığını ima edecek sorunları çözmek için algoritmalar temelde kararsız olmalıdır.

Örneğin, paradokslar şunlardır:

Örnek 1:

Hilbert'in 10. problemi.

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

Keyfi 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 özel 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 uyumunu kontrol edin.

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

Örnek 2:

Fermat teoremi:

Böyle bir tamsayı yok A, B, s, n (N>2) , bunun için eşitlik

BİR + milyar = cn

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

Örnek 3:

Goldbach sorunu.

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

Her tam sayı 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ıklıkla bir çözüm önerdi: hatta N bu problem çözülebilir ve iki basit terime ayrıştırmaya eşdeğerdir.

I. Vinogradov, 1937'de bunu tuhaf bir şekilde kanıtladı Nüç asal terim bulmak mümkündür, ancak çift sayılar için çözüm şu ana kadar bulunamamıştır.

atama	Sezgisel açıklama	Tanım
	F bir fonksiyon tarafından yukarıdan sınırlı G	stil="maks-genişlik: %98; yükseklik: otomatik; genişlik: otomatik;" src="/pictures/wiki/files/101/eebfe73c29ff3f9bc886d263bd3e91f3.png" border="0"> veya style="max-width: %98; yükseklik: otomatik; genişlik: otomatik;" src="/pictures/wiki/files/100/d96907f9d7419a7e0c74e4089c35c35e.png" border="0">
	F fonksiyon tarafından aşağıdan sınırlı G(sabit bir faktöre kadar) asimptotik olarak	stil="maks-genişlik: %98; yükseklik: otomatik; genişlik: otomatik;" src="/pictures/wiki/files/48/0fda981f377ae7b8d361f58ce148c173.png" border="0">
	F yukarıdan ve aşağıdan bir fonksiyonla sınırlandırılmış G asimptotik olarak	0), n_0: \forall (n>n_0) \; |Cg(n)|
	G hakim F asimptotik olarak	stil="maks-genişlik: %98; yükseklik: otomatik; genişlik: otomatik;" src="/pictures/wiki/files/49/176ce786e936badb831a0bb87f25249d.png" border="0">
	F hakim G asimptotik olarak	stil="maks-genişlik: %98; yükseklik: otomatik; genişlik: otomatik;" src="/pictures/wiki/files/53/554bc3f42cfa6d0638722e58e4a99d8b.png" border="0">
	F eşdeğerdir G asimptotik olarak

örnekler

Notlar

En kötü yürütme süresinin büyüme oranının, algoritmaları ve programları değerlendirmek için tek veya en önemli kriter olmadığı vurgulanmalıdır. Çalışma zamanı ölçütüne başka bakış açılarından bakmanıza olanak tanıyan birkaç husus aşağıda verilmiştir:

Bir n-köşe grafiği için bir problemin çözümü, bir algoritma ile n C mertebesinde zaman (adım sayısı) ve başka bir - n+n!/C mertebesinde zaman (adım sayısı) alıyorsa, burada C sabit bir sayıdır , o zaman "polinom ideolojisine" göre birinci algoritma pratik olarak etkilidir ve ikincisi değildir, ancak örneğin C = 10'da (10 10) durum tam tersidir.

1. Verimli ancak karmaşık algoritmalar şu durumlarda istenmeyebilir: hazır programlar bu programların yazılmasına dahil olmayan kişileri destekleyecektir. Verimli algoritmalar oluşturmak için teknolojinin temel noktalarının yaygın olarak bilindiğini ve pratikte oldukça karmaşık algoritmaların özgürce uygulandığını umalım. Bununla birlikte, etkili, ancak "zor" algoritmaların, karmaşıklıkları ve bunları çözmeye çalışırken ortaya çıkan zorluklar nedeniyle rağbet görmeme olasılığını öngörmek gerekir.
2. birkaç örnek var verimli algoritmalar o kadar büyük miktarda makine belleği gerektirir (daha yavaş harici depolama ortamı kullanma olasılığı olmadan), bu faktör algoritmanın "verimlilik" avantajını ortadan kaldırır.
3. Sayısal algoritmalarda, algoritmaların doğruluğu ve kararlılığı, zaman verimliliklerinden daha az önemli değildir.

Zorluk sınıfları

Bir karmaşıklık sınıfı, hesaplama karmaşıklığında benzer algoritmaların olduğu bir dizi tanıma problemidir. İki önemli temsilci:

Sınıf P

P ve NP sınıflarının eşitlik sorunu

ünlü bilim adamları

• Leonid Levin
• Alexander Razborov
• Edie Sheimir

Ayrıca bakınız

Bağlantılar

• Yuri Lifshits "Teorik bilişimin modern sorunları". NP-zor problemler için algoritmalar üzerine dersler.
• A. A. Razborov Teorik Bilgisayar Bilimi: matematikçinin görüşü // bilgisayar. - 2001. - 2 numara. (alternatif bağlantı)
• A. A. Razborov Hesaplamaların karmaşıklığı üzerine // matematik eğitimi. - MTSNMO, 1999. - No. 3. - S. 127-141.

Wikimedia Vakfı. 2010

Diğer sözlüklerde "Algoritmanın zaman karmaşıklığı" nın ne olduğuna bakın:

zaman karmaşıklığı (algoritmanın)- - Konu bilgileri koruma EN zaman karmaşıklığı ... Teknik Tercümanın El Kitabı

OPERATÖR FAALİYETLERİNİN KARMAŞIKLIĞI- bir kişinin HMS'de gerekli işlevleri yerine getirme kalitesini ve süresini etkileyen bir dizi nesnel faktör. Bu yüzden. her biri belirli bir şekilde faktörlerin bir kombinasyonu ile karakterize edilen birkaç türe ayrılmıştır ... ... Ansiklopedik Psikoloji ve Pedagoji Sözlüğü

Algoritmayı ilk verilere uygulama süreçlerinin zorluğunun (hantallığının) sayısal bir tahminini veren bir hesaplama işlevi. A. ile arıtma. hesaplamalar, bir sinyal fonksiyonu (veya sadece bir sinyal fonksiyonu) kavramıdır, kenara verilir ... ... Matematiksel Ansiklopedi

Bilgisayar biliminde ve algoritma teorisinde, bir algoritmanın hesaplama karmaşıklığı, bazı algoritmalar tarafından gerçekleştirilen iş miktarının girdi verilerinin boyutuna bağımlılığını belirleyen bir işlevdir. Hesaplama karmaşıklığını inceleyen bölüme teori denir ... ... Wikipedia

Bilgisayar biliminde, hesaplama karmaşıklığı teorisi, bir hesaplama problemini çözmek için gereken işin maliyetini inceleyen hesaplama teorisinin bir dalıdır. Maliyet genellikle soyut zaman ve mekan kavramlarıyla ölçülür ... ... Vikipedi

Bu, bir listedeki öğeleri sıralamak için bir algoritmadır. Bir liste öğesinin birden fazla alanı olması durumunda, sıralama kriteri olarak işlev gören alana sıralama anahtarı adı verilir. Uygulamada, bir sayı genellikle bir anahtar görevi görür ve diğer alanlarda ... ... Wikipedia

Sıralama algoritması, bir listedeki öğeleri sıralamak için kullanılan bir algoritmadır. Bir liste öğesinin birden fazla alanı olması durumunda, sıralama kriteri olarak işlev gören alana sıralama anahtarı adı verilir. Uygulamada, bir sayı genellikle bir anahtar görevi görür ve ... ... Wikipedia'da

- (GM) şifreleme sistemi ile Genel anahtar Shafi Goldwasser ve Silvio Micali tarafından 1982 yılında geliştirilmiştir. GM, standart şifreleme altında kanıtlanabilir şekilde güvenli olan ilk açık anahtarlı olasılıksal şifreleme şemasıdır ... ... Vikipedi Daha fazlasını oku