Zaman karmaşıklığının gösterimi, analizi ve hesaplama yöntemleri ... Bu makale size zaman karmaşıklığını gösterecek
Yazar | OverRedMaple
Editör | Carol
Kaynak | CSDN Blogu
Mühür resmi | Oriental IC'de CSDN ücretli indirme
Hala zaman karmaşıklığını ve uzay karmaşıklığını nasıl hesaplayacağınızı merak ediyorsanız, o zaman doğru yere geldiniz!
Sözlük:
Bilgisayar biliminde, zaman karmaşıklığı aynı zamanda zaman karmaşıklığı olarak da adlandırılır.Bir algoritmanın zaman karmaşıklığı, algoritmanın çalışma süresini niteliksel olarak tanımlayan bir fonksiyondur. Bu, algoritmanın girdi değerini temsil eden dizge uzunluğunun bir fonksiyonudur. Zaman karmaşıklığı, genellikle bu fonksiyonun düşük dereceli terimi ve ilk katsayısı hariç, büyük O gösterimiyle ifade edilir. Bu şekilde, zaman karmaşıklığının asimtotik olduğu, yani girdi değeri sonsuza yaklaştığı zaman söylenebilir.
Zaman karmaşıklığının temsili
Aslında, algoritmanın (kodun) yürütme verimliliği ve algoritma kodunun yürütme süresidir. Aşağıdaki basit koda bakalım:
int sumFunc (int n) {int num = 0; // için bir kez çalıştır (int i = 1; i < = n; ++ i) {// n kere çalıştır num = num + i; // n kere çalıştır} return num;}
Her kod satırının yürütme zamanının t olduğunu varsayarsak, bu kod parçasının zamanı (2n + 2) * t
Kod yürütme süresi T (n) kod çalıştırma sayısı ile orantılıdır!
Öyleyse bir sonraki örneğe bakalım:
int sumFunc (int n) {int num = 0; // için bir kez çalıştır (int i = 1; i < = n; ++ i) {// (int j = 1; j için n kez çalıştır < = n; ++ j) {// n * n kez çalıştır num = num + i * j; // n * n kez çalıştır}}}
Benzer şekilde, kod yürütme zamanı (2n * n + n + 1) * t, değil mi? Geriye bakmaya devam edin!
Not: Veri yapısında / algoritmada, T (n) genellikle kod yürütme süresini temsil etmek için kullanılır, n veri boyutunu ve f (n) kod yürütme zamanlarının sentezidir, bu nedenle yukarıdaki örnek şu şekilde ifade edilebilir: f (n) = (2n * n + n + 1) * t , Aslında toplamı bulmak için bir formüldür Ö (Büyük O), kod yürütme süresi anlamına gelir ve f (n) Orantılı olarak.
Yukarıdaki iki örneğe dayanarak sonuçlar çıkarın: Kodun yürütme süresi T (n), her kod satırının yürütme sayısı ile orantılıdır n , İnsanlar bu yasayı şöyle bir formülle özetliyor: T (n) = O (f (n))
Dolayısıyla, ilk örnekte T (n) = O (2n + 1), ikinci örnekte T (n) = O (2n * n + n + 1), bu zaman karmaşıklığı gösterimi , Big O zaman karmaşıklığı gösterimi olarak da adlandırılır.
fakat, Büyük O zaman karmaşıklığı Kodu belirtmiyor Gerçek uygulama süresi Ama şu anlama gelir Veri ölçeğindeki artışla birlikte kod yürütme süresinin trendi Yani aynı zamanda Aşamalı zaman karmaşıklığı , Başvuruldu zaman karmaşıklığı .
Taylor'ın formülünün aksine, unut gitsin, nerede ...
N büyüdükçe ve büyüdüğünde, formüldeki düşük dereceli, sabit ve katsayının üç bölümü büyüme eğilimini etkileyemez, bu nedenle bunları doğrudan görmezden gelebilir ve yalnızca en büyük büyüklüğü kaydedebilirsiniz, bu nedenle yukarıdaki iki örnek Aslında zaman karmaşıklıkları şu şekilde kaydedilmelidir: T (n) = O (n), T (n) = O (n * n)
Bence neler olup bittiğini kabaca anlamalısın, o halde nasıl hesaplayacağımızı görelim?
Zaman karmaşıklığının analizi ve hesaplama yöntemi
(1) Maksimum döngü sayısı ilkesi
Yukarıda söylediğimiz gibi, n büyüdükçe, formüldeki düşük mertebeli, sabit ve katsayının üç parçası büyüme trendini etkileyemez, onları doğrudan görmezden gelebilir ve en büyük büyüklüğü kaydedebilirsiniz. Dolayısıyla, zaman karmaşıklığını hesapladığımızda, En fazla döngüye sahip koda odaklanmanız yeterlidir.
int sumFunc (int n) {int sum = 0; // Bir kez çalıştır, görmezden gel (int i = 0; i < n; i ++) {sum + = i; // Döngüdeki yürütme sayısı en fazladır ve yürütme sayısı n kattır, bu nedenle zaman karmaşıklığı O (n)} dönüş toplamı olarak kaydedilir; // 1 yürütme, yok sayılır}(2) Ekleme ilkesi
int sumFunc (int n) {int sum = 0; // sabit düzey, göz ardı edilir (int i = 0; i < 99; i ++) {toplam + = i; // 100 kez çalıştır, hala sabit seviyede, yok say} for (int i = 0; i < n; i ++) {toplam + = i; // n kez çalıştır} for (int i = 0; i < n; i ++) {for (int j = 0; j < n; j ++) {toplam + = i; // n * n kez çalıştır}} dönüş toplamı;}Yukarıdaki örnekte, en büyük iki kod parçasının zaman karmaşıklığı sırasıyla O (n) ve O (n * n) şeklindedir. Sonuç şöyle olmalıdır: T (n) = O (n) + O (n * n), biz En büyük büyüklüğü alın, böylece tüm kodun karmaşıklığı: O (n * n)
Öyleyse sonuca varın: En büyük büyüklüğe sahip kodun zaman karmaşıklığı = toplam zaman karmaşıklığı
(3) Çarpma prensibi
Yuvalanmış kodun karmaşıklığı, yuvanın içindeki ve dışındaki kodun karmaşıklığının ürününe eşittir.
void Func1 (int n) {for (int i = 0; i < n; i ++) {Func2 (n); // n kez çalıştır, her defasında Func2 işlevi n kez çağrılacak ve çalıştırılacak}} void Func2 (int n) {int sum = 0; for (int i = 0; i < n; i ++) {toplam + = 1; // n kez çalıştır}}Bu nedenle, bu kodun zaman karmaşıklığı O (n) * O (n) = O (n * n) = O (n * n)
Benzer şekilde, n'den biri m ile değiştirilirse, zaman karmaşıklığı O (n * m) olur.
Ortak zaman karmaşıklığı
(1) O (1) Sabit düzeyde zaman karmaşıklığı
void Func (void) {for (int i = 0; i < 100; i ++) {printf ("merhaba"); // O (1)}} void Func (void) {printf ("merhaba"); printf ("merhaba") ; printf ("merhaba"); // Her seferinde çalıştır, yine O (1) olarak kaydedilir}Anlayabileceğine inanıyorum. O (1) tek bir kod satırı olduğu anlamına gelmez. Bu 1 bir sabiti temsil eder. Daha önce 10.000 satır olsa bile O (1) 'dir çünkü sabittir ve değişmeyecektir ( Bu sabittir), Bu nedenle, tüm sabit düzey karmaşıklık kodları O (1) olarak kaydedilir.
(2) Ortak O (n) karmaşıklığı
void Func (int n) {for (int i = 0; i < n; i ++) {printf ("merhaba");}}Söylemeye gerek yok! sürdürmek!
(3) O (logn), O (nlogn), bu biraz zor!
Öncelikle aşağıdaki dip takas formülünü hatırlayalım:
Formülü hatırlayın, bir örneğe bakın:
void Func (int n) {for (int i = 1; i < n; i ++) {i = i * 2;}}Görülüyor ki i = i * 2 kod satırının en çok çalıştırıldığı, peki kaç kere çalıştırıldı?
İlk kez i = 2, ikinci kez i = 4, üçüncü kez i = 8 ...
Diyelim ki x kez yürütüldü, sonra x'in değeri:
Yukarıdaki koddaki 2, 3 olarak değiştirildiğinde, x'in değeri de:
Elbette, günlüğün tabanı ne olursa olsun, e veya 10 olsun, hepsi şu şekilde kaydedilir:
Bu neden? Alttan değişen formülden hesaplanabilir:
Tabanı değiştirdikten sonra, log3 (2) 'nin aslında sabit olduğunu görebiliriz, görmezden gelin! Bu oyunda, günlük varsayılan olarak 2 tabanına ayarlıdır, bu nedenle tümü O (logn) olarak kaydedilir.
void Func (int n) {for (int i = 0; i < n; i ++) {Func2 (n); // n kez çalıştır, iç içe çağrılar, her çağrı için logn kez çalıştır}} void Func2 (int n) {for (int i = 0; i < n; i ++) {i = i * 2; // oturum açma zamanlarını çalıştır}}Yani bu O (nlogn) 'un anlaşılması da kolaydır!
