ÔÇťB├╝y├╝k OÔÇŁ yaz─▒m─▒na dair basit bir ─░ngilizce a├ž─▒klama nedir?


Al─▒nan cevaba git


Olabildi─čince az resmi tan─▒m─▒ ve basit matemati─či tercih ederim.


4827









Cevap say─▒s─▒n─▒ say: 30






H─▒zl─▒ not, bu neredeyse kesinlikle Big O notasyonunu (bir ├╝st s─▒n─▒rd─▒r) Theta notasyonu ile ÔÇť╬śÔÇŁ (iki tarafl─▒ bir s─▒n─▒rd─▒r) ile kar─▒┼čt─▒r─▒r. Deneyimlerime g├Âre, bu asl─▒nda akademik olmayan ortamlardaki tart─▒┼čmalar─▒n tipik bir ├Ârne─či. Herhangi bir kar─▒┼č─▒kl─▒ktan dolay─▒ ├Âz├╝r dileriz.


B├╝y├╝k O karma┼č─▒kl─▒─č─▒ bu grafikle g├Ârselle┼čtirilebilir:


B├╝y├╝k O Analizi

Big-O notasyonu i├žin verebilece─čim en basit tan─▒m ┼čudur:

Big-O notasyonu bir algoritman─▒n karma┼č─▒kl─▒─č─▒n─▒n g├Âreceli bir temsilidir.

Bu c├╝mlede baz─▒ ├Ânemli ve kasten se├žilmi┼č kelimeler var:

  • g├Âreceli: sadece elmalar─▒ elmalar ile kar┼č─▒la┼čt─▒rabilirsiniz. Aritmetik ├žarpma yapmak i├žin bir algoritmay─▒, tamsay─▒lar─▒n listesini s─▒ralayan bir algoritma ile kar┼č─▒la┼čt─▒ramazs─▒n─▒z. Ancak aritmetik i┼člem yapmak i├žin iki algoritman─▒n kar┼č─▒la┼čt─▒r─▒lmas─▒ (bir ├žarpma, bir toplama) size anlaml─▒ bir ┼čey s├Âyleyecektir;
  • Temsil: Big-O (en basit haliyle), algoritmalar aras─▒ndaki kar┼č─▒la┼čt─▒rmay─▒ tek bir de─či┼čkene indirger. Bu de─či┼čken g├Âzlemlere veya varsay─▒mlara g├Âre se├žilir. ├ľrne─čin, s─▒ralama algoritmalar─▒ genellikle kar┼č─▒la┼čt─▒rma i┼člemlerine dayanarak kar┼č─▒la┼čt─▒r─▒l─▒r (ba─č─▒l s─▒ralamalar─▒n─▒ belirlemek i├žin iki d├╝─č├╝m├╝ kar┼č─▒la┼čt─▒rarak). Bu, kar┼č─▒la┼čt─▒rman─▒n pahal─▒ oldu─čunu varsayar. Peki ya kar┼č─▒la┼čt─▒rma ucuzsa, ama takas pahal─▒ysa? Kar┼č─▒la┼čt─▒rma de─či┼čtirir; ve
  • karma┼č─▒kl─▒k: 10.000 elementi s─▒ralamak bir saniyemi al─▒rsa bir milyonu ay─▒rmam ne kadar s├╝rer? Bu durumda karma┼č─▒kl─▒k ba┼čka bir ┼čey i├žin g├Âreceli bir ├Âl├ž├╝d├╝r.

Gerisini okudu─čunuzda geri gelin ve yukar─▒dakileri tekrar okuyun.

Akl─▒ma gelen en b├╝y├╝k ├Ârnek, aritmetik i┼člemdir. ─░ki numara al (123456 ve 789012). Okulda ├Â─črendi─čimiz temel aritmetik i┼člemler ┼čunlard─▒:

  • ilave;
  • ├ž─▒karma;
  • ├žarpma i┼člemi; ve
  • b├Âl├╝nme.

Bunlar─▒n her biri bir operasyon veya bir problemdir. Bunlar─▒ ├ž├Âzme y├Ântemine algoritma denir .

Toplama en basit olan─▒d─▒r. Say─▒lar─▒ yukar─▒ do─čru (sa─ča do─čru) hizalar ve rakamlar─▒, sonu├žta bu eklemenin son say─▒s─▒n─▒ yazan bir s├╝tuna ekleyin. Bu say─▒n─▒n ÔÇťonlarcaÔÇŁ k─▒sm─▒ bir sonraki s├╝tuna ta┼č─▒n─▒r.

Bu say─▒lar─▒n eklenmesinin bu algoritmada en pahal─▒ i┼člem oldu─čunu varsayal─▒m. Bu iki rakam─▒ bir araya getirmek i├žin 6 rakam─▒ bir araya getirmemiz gerekecek (ve muhtemelen 7'inci). ─░ki basamakl─▒ 100 rakam─▒ bir araya getirirsek, 100 ekleme yapmam─▒z gerekir. ─░ki adet 10.000 rakam eklersek, 10.000 adet ekleme yapmam─▒z gerekir.

Deseni g├Âr├╝yor musun? Karma┼č─▒kl─▒─č─▒ (i┼člemlerin say─▒s─▒n─▒ olmak ├╝zere) basamak say─▒s─▒ ile do─čru orant─▒l─▒d─▒r , n daha ├žok say─▒da. Buna O (n) veya do─črusal karma┼č─▒kl─▒k diyoruz .

├ç─▒karma benzer (ta┼č─▒ma yerine ├Âd├╝n├ž alman─▒z gerekmeyebilir).

├çarpma farkl─▒. Numaralar─▒ s─▒ralars─▒n─▒z, alt numaradaki ilk basama─č─▒ al─▒n ve ├╝st basamaktaki her basama─ča g├Âre s─▒rayla ├žarp─▒n ve her bir basama─ča kadar devam edin. Bu y├╝zden iki 6 haneli say─▒m─▒z─▒ ├žarpmak i├žin 36 ├žarp─▒m yapmal─▒y─▒z. Son sonucu almak i├žin 10 veya 11 s├╝tun eklemesi yapmam─▒z gerekebilir.

─░ki basamakl─▒ iki rakam─▒m─▒z varsa, 10.000 ├žarpma ve 200 ek yapmam─▒z gerekir. ─░ki milyon rakam i├žin bir trilyon (10 12 ) ├žarpma ve iki milyon ek yapmam─▒z gerekiyor .

Algoritma n kare ile ├Âl├žeklendi─činde , bu O (n 2 ) veya ikinci dereceden karma┼č─▒kl─▒kt─▒r . Bu, ba┼čka bir ├Ânemli konsepti tan─▒tmak i├žin iyi bir zamand─▒r:

Biz sadece karma┼č─▒kl─▒─č─▒n en ├Ânemli k─▒sm─▒n─▒ ├Ânemsiyoruz.

Astute, operasyon say─▒s─▒n─▒ ┼ču ┼čekilde ifade edebilece─čimizi fark etmi┼č olabilir: n 2 + 2n. Ancak ├Ârne─čimizde iki milyon rakam olan iki rakam g├Ârd├╝─č├╝n├╝zde, ikinci terim (2n) ├Ânemsiz hale gelir (bu a┼čamadaki toplam i┼člemlerin% 0.0002'sini olu┼čturur).

Buradaki en k├Ât├╝ senaryoyu ald─▒─č─▒m─▒z─▒ fark edebilirsiniz. Biri 4 basamakl─▒, di─čeri 6 basamakl─▒ ise 6 basamakl─▒ say─▒lar─▒ ├žarparken sadece 24 ├žarp─▒m─▒m─▒z var. Yine de, 'n' i├žin en k├Ât├╝ durum senaryosunu, yani her ikisi de 6 basamakl─▒ say─▒ oldu─čunda hesapl─▒yoruz. Bu nedenle Big-O notasyonu bir algoritman─▒n en k├Ât├╝ senaryosu hakk─▒ndad─▒r.

Telefon rehberi

Akl─▒ma gelen en iyi ├Ârnek, normalde Beyaz Sayfalar veya benzeri olarak adland─▒r─▒lan, ancak ├╝lkeden ├╝lkeye de─či┼čecek olan telefon rehberidir. Ama ben insanlar─▒ soyad─▒na g├Âre listeleyen ve sonra ba┼č harflerini ya da adlar─▒n─▒, muhtemelen adreslerini ve telefon numaralar─▒n─▒ s├Âyleyenlerden bahsediyorum.

┼×imdi, bir bilgisayara "John Smith" telefon numaras─▒n─▒ 1000.000 isim i├žeren bir telefon rehberinde arama talimat─▒ verirseniz ne yapard─▒n─▒z? SÔÇÖnin ne kadar ba┼člad─▒─č─▒n─▒ tahmin edebilece─činiz ger├že─čini g├Âz ard─▒ ederek (yapamayaca─č─▒n─▒z─▒ varsayal─▒m), ne yapard─▒n─▒z?

Tipik bir uygulama, merkeze a├ž─▒lmak, 500.000'inci s─▒ray─▒ almak ve "Smith" ile kar┼č─▒la┼čt─▒rmak olabilir. E─čer "Smith, John" olacaksa, ├žok ┼čansl─▒yd─▒k. ├çok daha b├╝y├╝k olas─▒l─▒kla "John Smith" bu isimden ├Ânce veya sonra olacak. E─čer ├Âyleyse, telefon rehberinin son yar─▒s─▒n─▒ ikiye b├Âl├╝p tekrarlay─▒n. ├ľnceden ├Âyleyse, telefon rehberinin ilk yar─▒s─▒n─▒ ikiye b├Âler ve tekrar ederiz. Ve bunun gibi.

Buna ikili arama denir ve bunu ger├žekle┼čtirip ger├žekle┼čtirmemeniz programlamada her g├╝n kullan─▒l─▒r.

Yani milyonlarca isimden olu┼čan bir telefon rehberinde bir isim bulmak istiyorsan─▒z, bunu en ├žok 20 kez yaparak herhangi bir isim bulabilirsin. Arama algoritmalar─▒n─▒ kar┼č─▒la┼čt─▒r─▒rken bu kar┼č─▒la┼čt─▒rman─▒n 'n' oldu─čuna karar veriyoruz.

  • 3 ismin bir telefon rehberi i├žin 2 kar┼č─▒la┼čt─▒rmas─▒ gerekir (en fazla).
  • 7 i├žin en fazla 3 al─▒r.
  • 15 i├žin 4 al─▒r.
  • ...
  • 1.000.000 i├žin 20 al─▒r.

Bu ┼ča┼č─▒rt─▒c─▒ derecede iyi de─čil mi?

B├╝y├╝k-O terimlerinde bu O (log n) veya logaritmik karma┼č─▒kl─▒kt─▒r . ┼×imdi s├Âz konusu logaritma ln (e ├╝ss├╝), log 10 , log 2 veya ba┼čka bir baz olabilir. Yine de O (log n) O (2n 2 ) ve O (100n 2 ) gibi hala O (n 2 ) oldu─ču ├Ânemli de─čil.

Bu noktada, Big O'nun bir algoritma ile ├╝├ž durumu belirlemek i├žin kullan─▒labilece─čini a├ž─▒klamakta fayda vard─▒r:

  • En ─░yi Durum: Telefon rehberi aramas─▒nda en iyi durum, ad─▒ bir kar┼č─▒la┼čt─▒rmada bulmam─▒zd─▒r. Bu, O (1) veya s├╝rekli karma┼č─▒kl─▒kt─▒r ;
  • Beklenen Durum: Yukar─▒da tart─▒┼č─▒ld─▒─č─▒ gibi, bu O (log n); ve
  • En K├Ât├╝ Durum: Bu da O (log n).

Normalde en iyi durum umurumuzda de─čil. Beklenen ve en k├Ât├╝ durumla ilgileniyoruz. Bazen bunlardan biri veya di─čeri daha ├Ânemli olabilir.

Telefon rehberine geri d├Ân.

Ya bir telefon numaran─▒z varsa ve bir isim bulmak istiyorsan─▒z? Polisin ters telefon rehberi var, ancak bu t├╝r aramalar genel halka reddedildi. Yoksa onlar m─▒? Teknik olarak normal bir telefon rehberindeki bir numaray─▒ ters ├ževirebilirsiniz. Nas─▒l?

─░lk addan ba┼člay─▒p numaray─▒ kar┼č─▒la┼čt─▒r─▒n. E─čer bir e┼čle┼čme, harika, de─čilse, bir sonrakine ge├žersiniz. Bu ┼čekilde yapmak zorundas─▒n─▒z ├ž├╝nk├╝ telefon rehberi s─▒ralanmam─▒┼č (zaten telefon numaras─▒yla).

Yani telefon numaras─▒ verilen bir ismi bulmak i├žin (geriye do─čru arama):

  • En ─░yi Durum: O (1);
  • Beklenen Durum: O (n) (500,000 i├žin); ve
  • En K├Ât├╝ Durum: O (n) (1,000,000 i├žin).

Gezgin Sat─▒c─▒

Bu, bilgisayar bilimlerinde olduk├ža ├╝nl├╝ bir sorundur ve bir haberi hak ediyor. Bu problemde N kentiniz var. Bu ┼čehirlerin her biri belli bir mesafedeki karayoluyla 1 veya daha fazla ba┼čka ┼čehre ba─čl─▒. Gezgin Sat─▒c─▒ problemi, her ┼čehri ziyaret eden en k─▒sa turu bulmak.

Kula─ča basit mi geliyor? Tekrar d├╝┼č├╝n.

3 ├žift A, B ve C ┼čehiriniz varsa, t├╝m ├žiftlerin aras─▒nda kalan yollar mevcutsa:

  • A Ôćĺ B Ôćĺ C
  • A Ôćĺ C Ôćĺ B
  • B Ôćĺ C Ôćĺ A
  • B Ôćĺ A Ôćĺ C
  • C Ôćĺ A Ôćĺ B
  • C Ôćĺ B Ôćĺ A

Asl─▒nda bundan daha az var ├ž├╝nk├╝ bunlardan baz─▒lar─▒ e┼čde─čerdir (A Ôćĺ B Ôćĺ C ve C Ôćĺ B Ôćĺ A e┼čde─čerdir, ├Ârne─čin, ayn─▒ yollar─▒, tam tersi kullan─▒yorlar ├ž├╝nk├╝).

Ger├žekte 3 olas─▒l─▒k vard─▒r.

  • Bunu 4 kasabaya g├Ât├╝r├╝n ve (iirc) 12 se├žene─činiz var.
  • 5 ile 60.
  • 6 360 olur.

Bu, fakt├Âriyel olarak adland─▒r─▒lan matematiksel i┼člemin bir i┼člevidir . Temelde:

  • 5! = 5 ├Ś 4 ├Ś 3 ├Ś 2 ├Ś 1 = 120
  • 6! = 6 ├Ś 5 ├Ś 4 ├Ś 3 ├Ś 2 ├Ś 1 = 720
  • 7! = 7 ├Ś 6 ├Ś 5 ├Ś 4 ├Ś 3 ├Ś 2 ├Ś 1 = 5040
  • ...
  • 25! = 25 ├Ś 24 ├ŚÔÇŽ ├Ś 2 ├Ś 1 = 15,511,210,043,330,985,984,000,000
  • ...
  • 50! = 50 ├Ś 49 ├ŚÔÇŽ ├Ś 2 ├Ś 1 = 3.04140932 ├Ś 10 64

Demek Gezici Sat─▒c─▒ probleminin B├╝y├╝k O'su O (n!) Ya da fakt├Âriyel ya da birle┼čtirici karma┼č─▒kl─▒kt─▒r .

200 ┼čehre ula┼čt─▒─č─▒n─▒z zaman, evrende sorunu geleneksel bilgisayarlarla ├ž├Âzmek i├žin yeterli zaman kalmaz.

D├╝┼č├╝nmek i├žin bir ┼čey.

Polinom Zaman─▒

Ben h─▒zl─▒ bahsetmek istedi─čim bir ba┼čka nokta bir karma┼č─▒kl─▒─č─▒ olan herhangi algoritma olmas─▒d─▒r O (n bir ) oldu─ču s├Âylenir polinom karma┼č─▒kl─▒─č─▒n─▒ veya ├ž├Âz├╝lebilir oldu─ču polinom zamanda .

O (n), O (n 2 vs.) polinom zaman vard─▒r. Polinom zaman─▒nda baz─▒ problemler ├ž├Âz├╝lemez. Bundan dolay─▒ d├╝nyada baz─▒ ┼čeyler kullan─▒l─▒yor. Genel Anahtar ┼×ifrelemesi en ├Ânemli ├Ârneklerden biridir. ├çok fazla say─▒da iki ana fakt├Âr bulmak ├žok zor. ├ľyle de─čilse, kulland─▒─č─▒m─▒z ortak anahtar sistemlerini kullanamad─▒k.

Her neyse, i┼čte bu b├╝y├╝k O (g├Âzden ge├žirilmi┼č) (benim a├ž─▒k s├Âzl├╝ ─░ngilizce) a├ž─▒klamam i├žin.


6465







Bir algoritman─▒n nas─▒l ├Âl├žeklendi─čini g├Âsterir.

O (n 2 ) : Kuadratik karma┼č─▒kl─▒k olarak bilinir

  • 1 ├Â─če: 1 saniye
  • 10 ├Â─če: 100 saniye
  • 100 ├╝r├╝n: 10000 saniye

├ľ─če say─▒s─▒n─▒n 10 kat artt─▒─č─▒na, ancak s├╝renin 10 2 kat artt─▒─č─▒na dikkat edin . Temel olarak, n = 10 ve O, b├Âylece (n 2 ) bize ├Âl├žeklendirme fakt├Âr├╝ N verir 2 10 2 .

O (n) : Do─črusal karma┼č─▒kl─▒k olarak bilinir.

  • 1 ├Â─če: 1 saniye
  • 10 ├Â─če: 10 saniye
  • 100 ├╝r├╝n: 100 saniye

Bu kez, madde say─▒s─▒ 10 kat artar ve zaman da artar. n = 10 ve dolay─▒s─▒yla O (n) 'in ├Âl├žeklendirme fakt├Âr├╝ 10'dur.

O (1) : Sabit karma┼č─▒kl─▒k olarak bilinir.

  • 1 ├Â─če: 1 saniye
  • 10 ├Â─če: 1 saniye
  • 100 ├╝r├╝n: 1 saniye

Maddelerin say─▒s─▒ hala 10 kat artmaktad─▒r, ancak O (1) 'in ├Âl├žeklendirme fakt├Âr├╝ her zaman 1'dir.

O (log n) : Logaritmik karma┼č─▒kl─▒k olarak bilinir

  • 1 ├Â─če: 1 saniye
  • 10 ├Â─če: 2 saniye
  • 100 ├Â─če: 3 saniye
  • 1000 ├╝r├╝n: 4 saniye
  • 10000 ├╝r├╝n: 5 saniye

Hesaplamalar─▒n say─▒s─▒ yaln─▒zca giri┼č de─čerinin g├╝nl├╝─č├╝ ile artt─▒r─▒l─▒r. Dolay─▒s─▒yla, bu durumda, her bir hesaplaman─▒n 1 saniye s├╝rd├╝─č├╝n├╝ varsayarsak, giri┼čin g├╝nl├╝─č├╝ n gerekli zamand─▒r, dolay─▒s─▒yla log n .

Bu onun ├Âz├╝. Matemati─či d├╝┼č├╝r├╝rler, b├Âylece tam olarak n 2 olmayabilir ya da her ne s├Âyleseler de olabilir , ama bu ├Âl├žeklemede bask─▒n fakt├Âr olacakt─▒r.


707







Big-O notasyonu (ayr─▒ca "asimptotik b├╝y├╝me" notasyonu da denir), orijin yak─▒n─▒ndaki sabit fakt├Ârleri ve maddeleri g├Âz ard─▒ etti─činizde "benzeyen" i┼člevdir . ┼×ey ├Âl├že─či hakk─▒nda konu┼čmak i├žin kullan─▒yoruz .


temeller

"yeterince" b├╝y├╝k giri┼čler i├žin ...

  • f(x) Ôłł O(upperbound) f "daha h─▒zl─▒ b├╝y├╝mez" anlam─▒na gelir upperbound
  • f(x) Ôłł Ăč(justlikethis) f "aynen b├Âyle b├╝y├╝r" demek justlikethis
  • f(x) Ôłł ╬ę(lowerbound) f "Daha yava┼č b├╝y├╝mez" anlam─▒na gelir lowerbound

big-O notasyonu s├╝rekli fakt├Ârleri ├Ânemsemez: i┼člevin 9x┬▓ "aynen ├Âyle oldu─ču" s├Âylenir 10x┬▓ . Big-O asimptotik g├Âsterimi asimptotik olmayan ┼čeylerle de ilgilenmez ("kayna─č─▒n yak─▒n─▒nda olan ┼čeyler" veya "sorun boyutu k├╝├ž├╝k oldu─čunda ne olur"): fonksiyonun 10x┬▓ "tam olarak ayn─▒ ┼čekilde b├╝y├╝d├╝─č├╝" s├Âylenir 10x┬▓ - x + 2 .

Denklemin daha k├╝├ž├╝k k─▒s─▒mlar─▒n─▒ neden g├Ârmezden gelmek istiyorsun? ├ç├╝nk├╝, daha b├╝y├╝k ve daha b├╝y├╝k ├Âl├žekler olarak kabul etti─činiz gibi, denklemin b├╝y├╝k k─▒s─▒mlar─▒ taraf─▒ndan tamamen c├╝ce hale gelirler; katk─▒lar─▒ c├╝ce ve ilgisiz hale gelir. (├ľrnek b├Âl├╝me bak─▒n─▒z.)

Ba┼čka bir deyi┼čle, her ┼čey sonsuzlu─ča giderken oranla ilgilidir . Ger├žek zaman─▒ O(...) harcarsan─▒z, b├╝y├╝k girdiler limitinde sabit bir fakt├Âr elde edersiniz. Sezgisel olarak bu mant─▒kl─▒: biri di─čerini elde etmek i├žin ├žarpabilirsiniz e─čer birbiri gibi "├Âl├žek" i┼člevler. Yani, s├Âyledi─čimizde ...

 actualAlgorithmTime(N) Ôłł O(bound(N))
                                       e.g. "time to mergesort N elements 
                                             is O(N log(N))"
 

... bu , "yeterince b├╝y├╝k" sorun boyutlar─▒ i├žin N (orijinin yak─▒n─▒ndaki maddeleri g├Âzard─▒ edersek), ┼č├Âyle bir sabit oldu─čunu (├Ârne─čin 2.5, tamamen yap─▒lm─▒┼č) ifade eder:

 actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
ÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇ < constant            ÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇ < 2.5 
       bound(N)                                    N log(N)         
 

Sabit bir├žok se├ženek var; genellikle ÔÇťen iyiÔÇŁ se├žim algoritman─▒n ÔÇťsabit fakt├Âr├╝ÔÇŁ olarak bilinir ... ancak ├žo─ču zaman en b├╝y├╝k olmayan terimleri g├Ârmezden geliriz (genellikle neden ├Ânemli olmad─▒klar─▒na dair Sabit Fakt├Ârler b├Âl├╝m├╝ne bak─▒n). Ayr─▒ca "diyerek ba─čl─▒ olarak yukar─▒daki denklemin d├╝┼č├╝nebiliriz , ge├žen s├╝re kabaca daha k├Ât├╝ olamaz k├Ât├╝ durum senaryosunda N*log(N) (sabit fakt├Âr├╝ biz ├žok umurumda de─čil) 2.5 kat i├žinde, " .

Genel O(...) olarak, en faydal─▒ olan─▒d─▒r ├ž├╝nk├╝ ├žo─ču zaman en k├Ât├╝ durum davran─▒┼č─▒n─▒ ├Ânemsiyoruz. f(x) ─░┼člemci veya bellek kullan─▒m─▒ gibi "k├Ât├╝" bir ┼čeyi temsil ediyorsa , " f(x) Ôłł O(upperbound) " upperbound i┼člemci / bellek kullan─▒m─▒n─▒n en k├Ât├╝ senaryosudur "anlam─▒na gelir .


Uygulamalar

Tamamen matematiksel bir yap─▒ olarak, b├╝y├╝k O notasyonu i┼člem s├╝resi ve haf─▒za hakk─▒nda konu┼čmakla s─▒n─▒rl─▒ de─čildir. ├ľl├žeklemenin anlaml─▒ oldu─ču yerlerde, asemptomiyi tart─▒┼čmak i├žin kullanabilirsiniz, ├Ârne─čin:

  • N Bir partideki insanlar aras─▒ndaki muhtemel el s─▒k─▒┼čmalar─▒n─▒n say─▒s─▒ ( Ăč(N┬▓) ├Âzellikle de N(N-1)/2 , ama ├Ânemli olan ┼čey "├Âl├žekler" olmas─▒ N┬▓ )
  • baz─▒ viral pazarlamay─▒ zaman─▒n bir fonksiyonu olarak g├Âren olas─▒l─▒kla beklenen insan say─▒s─▒
  • web sitesi gecikmesi bir CPU veya GPU veya bilgisayar k├╝mesindeki i┼člem birimi say─▒s─▒yla nas─▒l ├Âl├žeklenir?
  • CPU ├╝zerindeki ─▒s─▒ ├ž─▒kt─▒s─▒ ├Âl├žeklerinin transist├Âr say─▒m─▒, voltaj vb. bir fonksiyon olarak nas─▒l ├Âld├╝─č├╝
  • Bir algoritman─▒n, giri┼č b├╝y├╝kl├╝─č├╝n├╝n bir fonksiyonu olarak ne kadar s├╝re ├žal─▒┼čmas─▒ gerekti─či
  • Bir algoritman─▒n giri┼č b├╝y├╝kl├╝─č├╝n├╝n bir fonksiyonu olarak ├žal─▒┼čmas─▒ i├žin ne kadar alan ├žal─▒┼čmas─▒ gerekti─či

├ľrnek

Yukar─▒daki el s─▒k─▒┼čma ├Ârne─či i├žin, bir odadaki herkes herkesin elini s─▒kar. Bu ├Ârnekte #handshakes Ôłł Ăč(N┬▓) ,. Niye ya?

Biraz yedekleyin: el s─▒k─▒┼čmalar─▒n─▒n say─▒s─▒ tam olarak n-select-2 veya N*(N-1)/2 (N ki┼čiden her biri N-1 di─čer ki┼čilerin ellerini s─▒kar, ancak bu sayede 2 b├Âl├╝ iki el s─▒k─▒┼čma say─▒s─▒):


herkes herkesin elini s─▒kar. Resim kredisi ve wikipedia / wikimedia commons ba┼č─▒na &quot;komple grafik&quot; makalesi.


biti┼čik matris

Ancak, ├žok say─▒da insan i├žin, do─črusal terim N c├╝cedir ve etkin bir ┼čekilde 0 oran─▒na katk─▒da bulunur (grafikte: kat─▒l─▒mc─▒lar─▒n say─▒s─▒ artt─▒k├ža, diyagonal ├╝zerindeki bo┼č kutular─▒n toplam kutulara oran─▒ daha k├╝├ž├╝k olur). Bu nedenle, ├Âl├žeklendirme davran─▒┼č─▒ order N┬▓ ya da el s─▒k─▒┼čmalar─▒n─▒n say─▒s─▒ "N┬▓ gibi artar".

 #handshakes(N)
ÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇ Ôëł 1/2
     N┬▓
 

Grafi─čin k├Â┼čegenindeki bo┼č kutular (N * (N-1) / 2 onay i┼čaretleri) sanki orada bile de─čildi ( asimptotik olarak N 2 onay i┼čaretleri).

("basit ─░ngilizce" den ge├žici kazma :) :) Bunu kendinize kan─▒tlamak isterseniz, bunu birden fazla terime ay─▒rma oran─▒nda basit bir cebir uygulayabilirsiniz ( lim "s─▒n─▒r─▒nda d├╝┼č├╝n├╝len" anlam─▒na gelir) g├Ârmedim, sadece "ve N ger├žekten ├žok b├╝y├╝k") i├žin g├Âsterimi:

     N┬▓/2 - N/2         (N┬▓)/2   N/2         1/2
lim ÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇ = lim ( ÔöÇÔöÇÔöÇÔöÇÔöÇÔöÇ - ÔöÇÔöÇÔöÇ ) = lim ÔöÇÔöÇÔöÇ = 1/2
NÔćĺÔł×     N┬▓       NÔćĺÔł×     N┬▓     N┬▓      NÔćĺÔł×  1
                               ÔöĽÔöüÔöüÔöüÔöÖ
             this is 0 in the limit of NÔćĺÔł×:
             graph it, or plug in a really large number for N
 

tl; dr: El s─▒k─▒┼čmalar─▒n─▒n say─▒s─▒, b├╝y├╝k de─čerler i├žin x┬▓'ye ├žok benziyor, e─čer # handshakes / x┬▓ oran─▒n─▒ yazsayd─▒k, tam olarak x┬▓ el s─▒k─▒┼čmalar─▒na ihtiya├ž duymad─▒─č─▒m─▒z ger├že─či ortaya ├ž─▒kmazd─▒. keyfi olarak b├╝y├╝k bir s├╝re i├žin ondal─▒kta.

├Ârne─čin, x = 1 milyon i├žin, # tokala┼čma oran─▒ / x┬▓: 0.499999 ...


Bina Sezgisi

Bu bize ┼č├Âyle a├ž─▒klamalar yapmam─▒z─▒ sa─člar ...

"Yeterli b├╝y├╝kl├╝kteki giri┼č boyutu = N ise, sabit fakt├Âr├╝ ne olursa olsun , giri┼č boyutunu iki kat─▒na ├ž─▒kar─▒rsam ...

  • ... Bir O (N) ("do─črusal zaman") algoritmas─▒n─▒n ald─▒─č─▒ s├╝reyi iki kat─▒na ├ž─▒kar─▒yorum. "

    N Ôćĺ (2N) = 2 ( N )

  • ... Bir O (N┬▓) ("kuadratik zaman") algoritmas─▒n─▒n harcad─▒─č─▒ s├╝reyi iki kat─▒na ├ž─▒kard─▒m (d├Ârt kat─▒na). " (├ľrne─čin, 100x b├╝y├╝kl├╝─č├╝nde 100x = 10000x b├╝y├╝kl├╝─č├╝nde ... muhtemelen s├╝rd├╝r├╝lemez)

    N┬▓ Ôćĺ (2N) ┬▓ = 4 ( N┬▓ )

  • ... bir O (N┬│) ("k├╝bik zaman") algoritmas─▒n─▒n ald─▒─č─▒ s├╝reyi iki kat─▒na ├ž─▒kard─▒m (eki). (├ľrne─čin, 100x b├╝y├╝kl├╝─č├╝nde 100x, 1000000x uzun s├╝rerse ... ├žok s├╝rd├╝r├╝lemez)

    cN┬│ Ôćĺ c (2N) ┬│ = 8 ( cN┬│ )

  • ... O (log (N)) ("logaritmik zaman") algoritmas─▒n─▒n ald─▒─č─▒ s├╝reye sabit bir miktar eklerim. (Ucuz!)

    c g├╝nl├╝─č├╝ (N) Ôćĺ c g├╝nl├╝─č├╝ (2N) = (c g├╝nl├╝─č├╝ (2)) + ( c g├╝nl├╝─č├╝ (N) ) = (sabit tutar) + ( c g├╝nl├╝─č├╝ (N) )

  • ... O (1) ("sabit zaman") algoritmas─▒n─▒n ald─▒─č─▒ zaman─▒ de─či┼čtirmem. " (En ucuz!)

    c * 1 Ôćĺ c * 1

  • ... Ben "(temel olarak)" O (N log (N)) algoritmas─▒n─▒n ald─▒─č─▒ s├╝reyi iki kat─▒na ├ž─▒kard─▒m. " (Olduk├ža yayg─▒n)

    temelde do─črusal olarak adland─▒rmak isteyebilece─činiz O'dan (N 1.000001 ) az

  • ... O (2 N ) ("├╝stel zaman") algoritmas─▒n─▒n harcad─▒─č─▒ zaman─▒ g├╝l├╝n├ž bir ┼čekilde art─▒r─▒yorum . " (Sorunu sadece tek bir ├╝nite art─▒rarak iki kat─▒na ├ž─▒kar─▒rs─▒n─▒z (veya ├╝├žl├╝ vb.).

    2 N Ôćĺ 2 2N = (4 N ) ............ ba┼čka bir yolla ...... 2 N Ôćĺ 2 N + 1 = 2 N 2 1 = 2 2 N

[matematiksel olarak e─čimli i├žin, k├╝├ž├╝k yan bo┼čluklar i├žin spoiler ├╝zerinde fare kullanabilirsiniz]

( https://stackoverflow.com/a/487292/711085ÔÇÖe verilen krediyle )

(teknik olarak sabit fakt├Âr baz─▒ ezoterik ├Ârneklerde belki ├Ânemli olabilir, ancak yukar─▒da belirtilenleri yazd─▒m (├Âr. log (N))

Bunlar, programc─▒lar─▒n ve uygulamal─▒ bilgisayar bilim adamlar─▒n─▒n referans noktalar─▒ olarak kulland─▒klar─▒ ekme ve tereya─čl─▒ b├╝y├╝me d├╝zenleri. Bunlar─▒ her zaman g├Âr├╝yorlar. (Bu nedenle, teknik olarak ÔÇťGirdiyi iki kat─▒na ├ž─▒karmak bir O (ÔłÜN) algoritmas─▒n─▒ 1.414 kat daha yava┼č yaparÔÇŁ diye d├╝┼č├╝nebilseniz de, bunun ÔÇťlogaritmikten daha k├Ât├╝ ama do─črusaldan daha iyiÔÇŁ oldu─čunu d├╝┼č├╝nmek daha iyidir.)


Sabit fakt├Ârler

Genelde belirli sabit fakt├Ârlerin ne oldu─ču umurumda de─čildir, ├ž├╝nk├╝ fonksiyonun b├╝y├╝me ┼čeklini etkilemezler. ├ľrne─čin, iki algoritman─▒n ikisinin de O(N) tamamlanmas─▒ zaman alabilir , ancak biri di─čerinden iki kat daha yava┼č olabilir. En iyi duruma getirme zor i┼č oldu─ču i├žin genellikle fakt├Âr ├žok b├╝y├╝k olmad─▒k├ža umrumda de─čil ( Optimizasyon ne zaman erken olur? ); ayr─▒ca daha iyi bir b├╝y├╝k-O ile bir algoritma se├žme eylemi genellikle b├╝y├╝kl├╝k s─▒ras─▒na g├Âre performans─▒ art─▒racakt─▒r.

Baz─▒ asimptotik olarak ├╝st├╝n algoritmalar (├Ârne─čin kar┼č─▒la┼čt─▒rmal─▒ olmayan bir O(N log(log(N))) s─▒ralama) o kadar b├╝y├╝k sabit bir fakt├Âre (├Ârne─čin 100000*N log(log(N)) ) veya O(N log(log(N))) bir gizli ile benzer ┼čekilde b├╝y├╝k bir tepeye sahip olabilir + 100*N , nadiren "b├╝y├╝k veriler" ├╝zerinde bile kullanmaya de─čerlerdir.


Neden O (N) bazen yapabilece─činizin en iyisidir, yani neden veri yap─▒lar─▒na ihtiyac─▒m─▒z var?

O(N) T├╝m verilerinizi okuman─▒z gerekirse, algoritmalar bir anlamda "en iyi" algoritmalard─▒r. Okuma ├žok hareket verilerinin bir demet bir oldu─čunu O(N) ├žal─▒┼čma. Belle─če y├╝klemek genellikle O(N) (veya donan─▒m deste─činiz varsa daha h─▒zl─▒d─▒r veya verileri zaten okuyorsan─▒z hi├ž vaktiniz yoktur). Ancak , her veri par├žas─▒na (veya di─čer t├╝m veri par├žalar─▒na) dokunursan─▒z veya hatta baksan─▒z bile, algoritman─▒z─▒n O(N) bu g├Âr├╝n├╝m├╝ ger├žekle┼čtirmesi zaman alacakt─▒r . As─▒l algoritman─▒z─▒n ne kadar s├╝rd├╝─č├╝n├╝ belirleyin, en az─▒ndan O(N) o zaman t├╝m verilere bakarak harcad─▒─č─▒ i├žin olacak .

Ayn─▒ ┼čey yazma eylemi i├žin de s├Âylenebilir . N ┼čeyi basan t├╝m algoritmalar N zaman alacakt─▒r, ├ž├╝nk├╝ ├ž─▒kt─▒ en az─▒ndan o kadar uzun (├Ârne─čin, t├╝m perm├╝tasyonlar─▒ (yeniden d├╝zenleme yollar─▒) basmak bir N oyun kart─▒ grubunun fakt├Âr├╝d├╝r O(N!) ).

Bu, veri yap─▒lar─▒n─▒n kullan─▒m─▒n─▒ motive eder : bir veri yap─▒s─▒, verileri yaln─▒zca bir kez (genellikle O(N) zaman) okumay─▒ , ayr─▒ca k├╝├ž├╝k tutmaya ├žal─▒┼čt─▒─č─▒m─▒z baz─▒ ├Ân i┼člemlerin (├Ârne─čin O(N) veya O(N log(N)) veya O(N┬▓) ) okumas─▒n─▒ gerektirir . Bundan sonra, veri yap─▒s─▒n─▒ de─či┼čtirmek (yerle┼čtirmeler / silmeler / vb.) Ve veriler ├╝zerinde sorgulamalar yapmak, O(1) veya gibi ├žok az zaman al─▒r O(log(N)) . Daha sonra ├žok say─▒da sorgu yapmaya devam edin! Genel olarak, ├Ânceden ne kadar ├žok i┼č yapmak istersen, daha sonra ne kadar az i┼č yapman gerekiyor?

├ľrne─čin, milyonlarca yol b├Âl├╝m├╝n├╝n enlem ve boylam koordinatlar─▒na sahip oldu─čunuzu ve t├╝m sokak kav┼čaklar─▒n─▒ bulmak istedi─činizi varsayal─▒m.

  • Naif y├Ântem: Bir sokak kesi┼čiminin koordinatlar─▒na sahipseniz ve yak─▒ndaki sokaklar─▒ incelemek istiyorsan─▒z, her seferinde milyonlarca segmentten ge├žmeniz ve her birinin biti┼čik olup olmad─▒─č─▒n─▒ kontrol etmeniz gerekir.
  • Bunu yaln─▒zca bir kez yapman─▒z gerekiyorsa, naif O(N) ├žal─▒┼čma y├Ântemini yaln─▒zca bir kez yapmak zorunda kalmazs─▒n─▒z, ancak bunu bir├žok kez yapmak istiyorsan─▒z (bu durumda, N her segment i├žin bir kez), biz O(N┬▓) ├žal─▒┼čmak zorunda kalacaks─▒n─▒z veya 1000000┬▓ = 1000000000000 i┼člemi. ─░yi de─čil (modern bir bilgisayar saniyede milyarlarca i┼člem yapabilir).
  • Bir karma tablosu (basit veya h─▒zl─▒ arama tablosu olarak da bilinen anl─▒k h─▒zl─▒ arama tablosu) ad─▒ verilen basit bir yap─▒ kullan─▒rsak, O(N) zaman i├žindeki her ┼čeyi ├Ânceden i┼čleyerek k├╝├ž├╝k bir ├╝cret ├Âderiz . Bundan sonra, anahtar─▒na g├Âre bir ┼čeyi aramak ortalama olarak yaln─▒zca zaman al─▒r (bu durumda, anahtar─▒m─▒z enlem ve boylam koordinatlar─▒d─▒r, bir ─▒zgaraya yuvarlan─▒r; sadece 9 olan biti┼čik bo┼čluklar─▒ arar─▒z; sabit).
  • G├Ârevimiz olanaks─▒z olandan O(N┬▓) y├Ânetilebilir hale geldi O(N) ve tek yapmam─▒z gereken bir karma tablo yapmak i├žin k├╝├ž├╝k bir bedel ├Âdemek oldu.
  • analoji : Bu ├Âzel durumdaki analoji bilmecenin bir par├žas─▒: Verinin baz─▒ ├Âzelliklerinden yararlanan bir veri yap─▒s─▒ olu┼čturduk. Yol b├Âl├╝mlerimiz puzzle par├žalar─▒ gibiyse, onlar─▒ renk ve desen e┼čle┼čtirerek grupland─▒r─▒r─▒z. Daha sonra fazladan ├žal─▒┼čmaktan ka├ž─▒nmak i├žin bundan yararlan─▒yoruz (benzer renkteki yapboz par├žalar─▒n─▒ di─čer her yapboz par├žas─▒na g├Âre de─čil, kar┼č─▒la┼čt─▒r─▒yoruz).

Hikayenin ahlaki: bir veri yap─▒s─▒, i┼člemleri h─▒zland─▒rmam─▒z─▒ sa─čl─▒yor. Daha geli┼čmi┼č veri yap─▒lar─▒ bile i┼člemleri ├žok zekice bir ┼čekilde birle┼čtirmenize, geciktirmenize ve hatta yok sayman─▒za izin verebilir. Farkl─▒ problemlerin farkl─▒ analojileri olur, ancak hepsi verileri ├Ânemseyen bir yap─▒y─▒ s├Âm├╝recek ya da defter tutma i├žin yapay olarak dayatt─▒─č─▒m─▒z ┼čekilde d├╝zenleyecek ┼čekilde d├╝zenlenmesini i├žerir. ├ľnceden i┼č yap─▒yoruz (temelde planlama ve d├╝zenleme) ve ┼čimdi tekrarlanan i┼čler ├žok daha kolay!


Pratik ├Ârnek: Kodlama s─▒ras─▒nda b├╝y├╝me d├╝zenlerini g├Ârselle┼čtirme

Asimptotik g├Âsterim, ├Âz├╝nde, programlamadan olduk├ža ayr─▒d─▒r. Asimptotik g├Âsterim, i┼člerin nas─▒l ├Âl├žeklendi─čini ve bir├žok farkl─▒ alanda kullan─▒labilece─čini d├╝┼č├╝nmeye y├Ânelik matematiksel bir ├žer├ževedir. Bu dedi ki ... kodlamaya asimptotik g├Âsterimi b├Âyle uygulars─▒n─▒z .

Temel bilgiler: Her boyut A koleksiyonunda (bir dizi, bir k├╝me, bir haritan─▒n t├╝m tu┼člar─▒ vb.) Koleksiyonundaki her bir ├Â─če ile etkile┼čime girdi─čimizde veya bir d├Âng├╝n├╝n A yinelemesini ger├žekle┼čtirdi─činde, bu A boyutunun ├žarp─▒msal bir fakt├Âr├╝ Neden "├žarp─▒msal fakt├Âr" diyorum? - ├ž├╝nk├╝ d├Âng├╝ler ve fonksiyonlar (neredeyse tan─▒m─▒ gere─či) ├žarp─▒msal ├žal─▒┼čma s├╝resine sahiptir: yineleme say─▒s─▒, d├Âng├╝de yap─▒lan ├žal─▒┼čma s├╝resi (veya fonksiyonlar i├žin: i┼člev, kez yap─▒lan i┼člerde i┼člev). (Bu, d├Âng├╝leri atlamak veya d├Âng├╝den erken ├ž─▒kmak veya herhangi bir yayg─▒n olan arg├╝manlara dayanarak fonksiyondaki kontrol ak─▒┼č─▒n─▒ de─či┼čtirmek gibi, fantezi bir ┼čey yapmazsak ge├žerlidir.) Burada, e┼člik eden s├Âzde kodla birlikte baz─▒ g├Ârselle┼čtirme teknikleri ├Ârnekleri verilmi┼čtir.

(burada, x s sabit zamanl─▒ ├žal─▒┼čma birimleri, i┼člemci talimatlar─▒, terc├╝man kodlar─▒, her neyse) temsil eder.

 for(i=0; i<A; i++)        // A * ...
    some O(1) operation     // 1

--> A*1 --> O(A) time

visualization:

|<------ A ------->|
1 2 3 4 5 x x ... x

other languages, multiplying orders of growth:
  javascript, O(A) time and space
    someListOfSizeA.map((x,i) => [x,i])               
  python, O(rows*cols) time and space
    [[r*c for c in range(cols)] for r in range(rows)]
 

├ľrnek 2:

 for every x in listOfSizeA:   // A * (...
    some O(1) operation         // 1
    some O(B) operation         // B
    for every y in listOfSizeC: // C * (...
        some O(1) operation       // 1))

--> O(A*(1 + B + C))
    O(A*(B+C))        (1 is dwarfed)

visualization:

|<------ A ------->|
1 x x x x x x ... x

2 x x x x x x ... x ^
3 x x x x x x ... x |
4 x x x x x x ... x |
5 x x x x x x ... x B  <-- A*B
x x x x x x x ... x |
................... |
x x x x x x x ... x v

x x x x x x x ... x ^
x x x x x x x ... x |
x x x x x x x ... x |
x x x x x x x ... x C  <-- A*C
x x x x x x x ... x |
................... |
x x x x x x x ... x v
 

├ľrnek 3:

 function nSquaredFunction(n) {
    total = 0
    for i in 1..n:        // N *
        for j in 1..n:      // N *
            total += i*k      // 1
    return total
}
// O(n^2)

function nCubedFunction(a) {
    for i in 1..n:                // A *
        print(nSquaredFunction(a))  // A^2
}
// O(a^3)
 

Biraz karma┼č─▒k bir ┼čey yaparsak, neler oldu─čunu g├Ârsel olarak hayal edebiliyor olabilirsiniz:

 for x in range(A):
    for y in range(1..x):
        simpleOperation(x*y)

x x x x x x x x x x |
x x x x x x x x x   |
x x x x x x x x     |
x x x x x x x       |
x x x x x x         |
x x x x x           |
x x x x             |
x x x               |
x x                 |
x___________________|
 

Burada, ├žizebilece─činiz en k├╝├ž├╝k ve belirgin taslak, ├Ânemli olan; bir ├╝├žgen iki boyutlu bir ┼čekildir (0.5 A ^ 2), t─▒pk─▒ bir kare gibi iki boyutlu bir ┼čekildir (A ^ 2); Burada ikisinin sabit fakt├Âr├╝, ikisi aras─▒ndaki asimptotik oranda kal─▒r, ancak t├╝m fakt├Ârler gibi onu g├Ârmezden geliriz ... (Bu tekni─čin i├žine girmedi─čim baz─▒ talihsiz n├╝anslar var; sizi yanl─▒┼č y├Ânlendirebilir.)

Elbette bu, d├Âng├╝lerin ve fonksiyonlar─▒n k├Ât├╝ oldu─ču anlam─▒na gelmez; Aksine, onlar modern programlama dillerinin yap─▒ ta┼člar─▒d─▒r ve biz onlar─▒ seviyoruz. Ancak, d├Âng├╝ler ve fonksiyonlar ile ko┼čullular─▒ dokuma y├Ântemimizin verilerimizle birlikte (kontrol ak─▒┼č─▒ vb.) Program─▒m─▒z─▒n zaman ve mekan kullan─▒m─▒n─▒ taklit etti─čini g├Âr├╝yoruz! Zaman ve mekan kullan─▒m─▒ bir sorun haline gelirse, o zaman zek├óya ba┼čvurdu─čumuzda ve b├╝y├╝me d├╝zenini bir ┼čekilde azaltmak i├žin g├Âz ├Ân├╝nde bulundurmad─▒─č─▒m─▒z bir algoritma veya veri yap─▒s─▒ bulduk. Bununla birlikte, bu g├Ârselle┼čtirme teknikleri (her zaman i┼če yaramasalar da) size en k├Ât├╝ durumda ├žal─▒┼čan bir zamanda saf bir tahminde bulunabilir.

─░┼čte g├Ârsel olarak tan─▒yabilece─čimiz ba┼čka bir ┼čey var:

 <----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x
x x x x x x x x
x x x x
x x
x
 

Bunu yeniden d├╝zenleyebilir ve O (N) oldu─čunu g├Ârebiliriz:

 <----------------------------- N ----------------------------->
x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x
x x x x x x x x x x x x x x x x|x x x x x x x x|x x x x|x x|x
 

Veya belki de O (N * log (N)) toplam s├╝re i├žin log (N) veriden ge├žer.

    <----------------------------- N ----------------------------->
 ^  x x x x x x x x x x x x x x x x|x x x x x x x x x x x x x x x x
 |  x x x x x x x x|x x x x x x x x|x x x x x x x x|x x x x x x x x
lgN x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x|x x x x
 |  x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x|x x
 v  x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x|x
 

─░lgisizce ama tekrar bahsetmeye de─čer: Bir karma i┼člemi ger├žekle┼čtirirsek (├Ârn. S├Âzl├╝k / ├Âzetlenebilir arama), bu O (1) fakt├Âr├╝d├╝r. Bu olduk├ža h─▒zl─▒.

 [myDictionary.has(x) for x in listOfSizeA]
 \----- O(1) ------/    

--> A*1 --> O(A)
 

├ľzyinelemeli bir i┼člev veya b├Âlme ve fethetme algoritmas─▒ gibi ├žok karma┼č─▒k bir ┼čey yaparsak , Master Teoremini (genellikle ├žal─▒┼č─▒r) veya g├╝l├╝n├ž durumlarda Akra-Bazzi Teoremini (neredeyse her zaman ├žal─▒┼č─▒r) kullanabilirsiniz. Algoritman─▒z─▒n ├žal─▒┼čma s├╝resi Wikipedia'da.

Ancak, programc─▒lar b├Âyle d├╝┼č├╝nmezler ├ž├╝nk├╝ sonu├žta algoritma sezgisi sadece ikinci nitelik kazan─▒r. Verimsiz bir ┼čeyi kodlamaya ba┼člayacaks─▒n─▒z ve hemen " fena halde verimsiz bir ┼čey mi yap─▒yorum ? " Diye d├╝┼č├╝neceksiniz . E─čer cevab─▒n─▒z "evet" ise ve bunun ger├žekten ├Ânemli oldu─čunu ├Âng├Âr├╝yorsan─▒z, o zaman bir ad─▒m geriye gidebilir ve i┼čleri daha h─▒zl─▒ y├╝r├╝tmek i├žin ├že┼čitli hileler d├╝┼č├╝nebilirsiniz (cevap neredeyse her zaman "bir karma tablo kullanmak", nadiren "bir a─ča├ž kullanmak" d─▒r. ve ├žok nadiren biraz daha karma┼č─▒k bir ┼čey).


─░tfa edilmi┼č ve ortalama durum karma┼č─▒kl─▒─č─▒

"─░tfa edilmi┼č" ve / veya "ortalama durum" kavram─▒ da vard─▒r (bunlar─▒n farkl─▒ oldu─čunu unutmay─▒n).

Ortalama Durum : Bu, bir fonksiyonun beklenen de─čeri i├žin, fonksiyonun kendisinden ziyade b├╝y├╝k O notasyonu kullanmaktan ibaret de─čildir. T├╝m girdilerin e┼čit derecede muhtemel oldu─čunu d├╝┼č├╝nd├╝─č├╝n├╝z her durumda, ortalama durum sadece ├žal─▒┼čma s├╝resinin ortalamas─▒d─▒r. ├ľrne─čin, quicksort ile, en k├Ât├╝ durum O(N^2) ger├žekten k├Ât├╝ girdiler i├žin olsa bile , ortalama durum ola─čand─▒r O(N log(N)) (ger├žekten k├Ât├╝ girdiler say─▒ca ├žok k├╝├ž├╝kt├╝r, ├žok az say─▒d─▒r, ortalama durumda onlar─▒ fark etmiyoruz).

─░tfa Edilen En K├Ât├╝ Durum : Baz─▒ veri yap─▒lar─▒ b├╝y├╝k olan en k├Ât├╝ durum karma┼č─▒kl─▒─č─▒na sahip olabilir, ancak bu i┼člemlerin ├žo─čunu yaparsan─▒z yapt─▒─č─▒n─▒z ortalama i┼č miktar─▒n─▒n en k├Ât├╝ durumdan daha iyi olaca─č─▒n─▒ garanti eder. ├ľrne─čin, normalde sabit O(1) zaman alan bir veri yap─▒n─▒z olabilir . Ancak, zaman zaman 'h─▒├žk─▒r─▒k' olacak ve O(N) bir rastgele i┼člem i├žin zaman alacakt─▒r , ├ž├╝nk├╝ belki de bir miktar defter tutma veya ├ž├Âp toplama faaliyeti yapmas─▒ gerekebilir ... ama e─čer h─▒├žk─▒r─▒rsa N i├žin tekrar h─▒├žk─▒rmayaca─č─▒na s├Âz verir. daha fazla i┼člem. En k├Ât├╝ durum maliyeti hala O(N) operasyon ba┼č─▒na ama itfa edilmi┼č maliyet bir├žok ishal ├╝zerinden oldu─ču O(N)/N = O(1) operasyonun ba┼č─▒na. B├╝y├╝k operasyonlar─▒n yeterince nadir olmas─▒ nedeniyle, ara s─▒ra yap─▒lan i┼čin b├╝y├╝k miktar─▒n─▒n, ├žal─▒┼čman─▒n geri kalan─▒yla sabit bir fakt├Âr olarak harcand─▒─č─▒ d├╝┼č├╝n├╝lebilir. ─░┼čin, asimptotik olarak ortadan kaybolacak kadar ├žok say─▒da ├ža─čr─▒da "itfa edildi─čini" s├Âyl├╝yoruz.

─░tfa edilmi┼č analiz analojisi:

Araba s├╝r├╝yorsun. Bazen, benzin istasyonuna gitmek i├žin 10 dakika ge├žirmeniz ve ard─▒ndan depoyu gaz ile doldurmak i├žin 1 dakika harcaman─▒z gerekir. Bunu araban─▒zla herhangi bir yere gitti─činizde yapt─▒ysan─▒z (benzin istasyonuna 10 dakika, bir galonun bir k─▒sm─▒n─▒ doldurarak birka├ž saniye ge├žirin), ├žok verimsiz olurdu. Ancak depoyu birka├ž g├╝nde bir doldurursan─▒z, benzin istasyonuna s├╝r├╝┼č i├žin harcanan 11 dakika, yeterince fazla say─▒da seferde "itfa edilir", bunu g├Ârmezden gelebilir ve t├╝m seyahatlerinizin belki de% 5 daha uzun oldu─čunu iddia edebilirsiniz.

Ortalama durum ile itfa edilmi┼č en k├Ât├╝ durum aras─▒ndaki kar┼č─▒la┼čt─▒rma:

  • Ortalama durum: Girdilerimizle ilgili baz─▒ varsay─▒mlarda bulunuyoruz; yani e─čer girdilerimizin farkl─▒ olas─▒l─▒klar─▒ varsa, o zaman ├ž─▒kt─▒lar─▒m─▒z / ├žal─▒┼čma s├╝relerinin farkl─▒ olas─▒l─▒klar─▒ olacakt─▒r (ki bunun ortalamas─▒n─▒ al─▒r─▒z). Genelde girdilerimizin hepsinin e┼čit derecede muhtemel oldu─čunu varsay─▒yoruz (tek tip olas─▒l─▒k), ancak ger├žek d├╝nyadaki girdiler "ortalama girdi" varsay─▒mlar─▒m─▒za uymuyorsa, ortalama ├ž─▒kt─▒ / ├žal─▒┼čma zaman─▒ hesaplamalar─▒ anlams─▒z olabilir. Tekd├╝ze rastgele girdileri olsa da beklentiniz varsa, bu d├╝┼č├╝nmenizde fayda var!
  • ─░tfa edilmi┼č en k├Ât├╝ durum: Amortize edilmi┼č en k├Ât├╝ durum veri yap─▒s─▒ kullan─▒yorsan─▒z, performans─▒n itfa edilmi┼č en k├Ât├╝ durum i├žinde olmas─▒ garanti edilir ... sonu├žta (girdiler, her ┼čeyi bilen ve denenmeye ├žal─▒┼čan k├Ât├╝ bir ┼čeytan taraf─▒ndan se├žilse bile) seni bo┼čver). Genellikle bunu beklenmedik b├╝y├╝k h─▒├žk─▒r─▒klarla performansta ├žok 'dalgal─▒' olan algoritmalar─▒ analiz etmek i├žin kullan─▒r─▒z, ancak zamanla di─čer algoritmalar─▒ da uygulay─▒n. (Bununla birlikte, veri yap─▒n─▒z ertelemeye istekli olan ├žok say─▒da ola─čan├╝st├╝ ├žal─▒┼čma i├žin ├╝st s─▒n─▒rlara sahip de─čilse, k├Ât├╝ bir sald─▒rgan sizi her seferinde maksimum ertelenmi┼č i┼č miktar─▒na yeti┼čmeye zorlayabilir.

Yine de, bir sald─▒rgan i├žin makul derecede endi┼čeleniyorsan─▒z , itfa ve ortalama durum d─▒┼č─▒nda endi┼čelenecek ba┼čka bir├žok algoritmik sald─▒r─▒ vekt├Âr├╝ vard─▒r.)

Hem ortalama durum hem de itfa, ak─▒lda ├Âl├žeklendirme ile d├╝┼č├╝nmek ve tasarlamak i├žin inan─▒lmaz derecede faydal─▒ ara├žlard─▒r.

( Bu alt konu ile ilgileniyorsan─▒z, ortalama durum ile itfa edilmi┼č analiz aras─▒ndaki farka bak─▒n─▒z.)


Çok boyutlu büyük O

├ço─ču zaman, insanlar i┼čte birden fazla de─či┼čken oldu─čunu anlam─▒yorlar. ├ľrne─čin, bir dize arama algoritmas─▒nda, algoritman─▒z zaman alabilir O([length of text] + [length of query]) , yani iki de─či┼čkende do─črusald─▒r O(N+M) . Di─čer daha saf algoritmalar O([length of text]*[length of query]) veya olabilir O(N*M) . Birden fazla de─či┼čkeni yoksaymak, algoritma analizinde g├Ârd├╝─č├╝m en yayg─▒n denetimlerden biri ve bir algoritma tasarlarken sizi engelleyebilir.


T├╝m hikaye

B├╝y├╝k O'nun t├╝m hikaye olmad─▒─č─▒n─▒ unutmay─▒n. ├ľnbelle─če alma, ├Ânbellekleri a├ž─▒k tutma, disk yerine RAM ile ├žal─▒┼čarak, paralelle┼čtirme kullanarak veya zaman─▒n ilerleyen i┼člerini yaparak engelleri kald─▒rarak baz─▒ algoritmalar─▒ b├╝y├╝k ├Âl├ž├╝de h─▒zland─▒rabilirsiniz - bu teknikler genellikle b├╝y├╝me s─▒ras─▒ndan ba─č─▒ms─▒zd─▒r "big-O" notasyonu, genellikle paralel algoritmalar─▒n big-no notasyonundaki ├žekirdek say─▒s─▒n─▒ g├Âreceksiniz.

Ayr─▒ca, program─▒n─▒z─▒n gizli k─▒s─▒tlamalar─▒ nedeniyle, asimptotik davran─▒┼č─▒ ger├žekten umursamayaca─č─▒n─▒z─▒ da unutmay─▒n. S─▒n─▒rl─▒ say─▒da de─čerle ├žal─▒┼č─▒yor olabilirsiniz, ├Ârne─čin:

  • 5 element gibi bir ┼čey O(N log(N)) s─▒ral─▒yorsan─▒z , h─▒zl─▒ quicksort'u kullanmak istemezsiniz ; K├╝├ž├╝k giri┼člerde iyi performans g├Âsteren ekleme t├╝r├╝n├╝ kullanmak istiyorsunuz. Bu durumlar genellikle, problemi yinelemeli s─▒ralama, h─▒zl─▒ Fourier d├Ân├╝┼č├╝mleri veya matris ├žarp─▒m─▒ gibi daha k├╝├ž├╝k ve daha k├╝├ž├╝k alt problemlere b├Âld├╝─č├╝n├╝z b├Âlme ve fethetme algoritmalar─▒nda ortaya ├ž─▒kar.
  • Baz─▒ de─čerler baz─▒ gizli ger├žeklerden dolay─▒ etkili bir ┼čekilde s─▒n─▒rland─▒r─▒lm─▒┼čsa (├Ârne─čin, ortalama bir insan ad─▒ belki de 40 harfle yumu┼čak bir ┼čekilde s─▒n─▒rlanm─▒┼č ve insan ya┼č─▒ yakla┼č─▒k 150'de yumu┼čak bir ┼čekilde s─▒n─▒rlanm─▒┼č). Ayr─▒ca terimleri etkili bir ┼čekilde sabit hale getirmek i├žin girdilerinize s─▒n─▒rlar koyabilirsiniz.

Uygulamada, ayn─▒ veya benzer asimptotik performansa sahip algoritmalar aras─▒nda bile, g├Âreceli de─čerleri asl─▒nda a┼ča─č─▒dakiler gibi ba┼čka ┼čeylerden kaynaklanabilir: di─čer performans fakt├Ârleri (quicksort ve mergesort ikisi de vard─▒r O(N log(N)) , ancak quicksort CPU ├Ânbelleklerinden yararlan─▒r); uygulama kolayl─▒─č─▒ gibi performans d─▒┼č─▒ hususlar; Bir k├╝t├╝phanenin mevcut olup olmad─▒─č─▒ ve k├╝t├╝phanenin ne kadar sayg─▒n ve muhafaza edildi─či.

Programlar, 2GHz bilgisayar vs 500MHz bir bilgisayarda daha yava┼č ├žal─▒┼čacakt─▒r. Bunu ger├žekten kaynak s─▒n─▒rlar─▒n─▒n bir par├žas─▒ olarak g├Ârm├╝yoruz, ├ž├╝nk├╝ ger├žek saniye ba┼č─▒na de─čil, makine kaynaklar─▒ a├ž─▒s─▒ndan (├Ârne─čin saat d├Âng├╝s├╝ ba┼č─▒na) ├Âl├žeklendirmeyi d├╝┼č├╝n├╝yoruz. Ancak, ├Âyk├╝nme alt─▒nda ├žal─▒┼č─▒yor olman─▒z veya derleyicinin kodu optimize edip etmemesi gibi performans─▒ 'gizlice' etkileyebilecek benzer ┼čeyler vard─▒r. Bunlar, baz─▒ temel i┼člemlerin daha uzun s├╝rmesine (hatta birbirine g├Âre olsa da) veya baz─▒ i┼člemleri asimptotik olarak (hatta birbirine g├Âre) h─▒zland─▒rabilir veya yava┼člatabilir. Etki, farkl─▒ uygulama ve / veya ├ževre aras─▒nda k├╝├ž├╝k veya b├╝y├╝k olabilir. Bu fazladan i┼či yapmak i├žin dilleri ya da makineleri de─či┼čtiriyor musunuz? Bu, y├╝zlerce ba┼čka nedene (gereklilik, beceriler, i┼č arkada┼člar─▒, programc─▒ ├╝retkenli─či, zaman─▒n─▒z─▒n parasal de─čeri, tan─▒d─▒kl─▒k, ge├žici ├ž├Âz├╝mler, neden montaj veya GPU de─čil, vb.) Performansa g├Âre daha ├Ânemli olabilir.

Programlama dili gibi yukar─▒daki konular neredeyse hi├ž bir zaman sabit fakt├Âr├╝n bir par├žas─▒ olarak kabul edilmezler (ya da olmamal─▒d─▒rlar); Ancak birileri onlar─▒n fark─▒nda olmal─▒d─▒r, ├ž├╝nk├╝ bazen (nadiren de olsa) baz─▒ ┼čeyleri etkileyebilir. ├ľrne─čin cpython'da, yerel ├Âncelik s─▒ras─▒ uygulamas─▒ asimptotik olarak optimal de─čildir ( ekleme veya bulma-min se├žiminiz O(log(N)) yerine O(1) ); ba┼čka bir uygulama kullan─▒yor musunuz Muhtemelen hay─▒r, ├ž├╝nk├╝ C uygulamas─▒ muhtemelen daha h─▒zl─▒ ve ba┼čka yerlerde de benzer sorunlar var. Travmalar var; bazen ├Ânemli ve bazen de de─čil.


( d├╝zenleme : "Basit ─░ngilizce" a├ž─▒klamas─▒ burada sona ermektedir.)

Matematik ek ad─▒

Taml─▒k i├žin, big-O notasyonunun kesin tan─▒m─▒ ┼ču ┼čekildedir: f(x) Ôłł O(g(x)) "f," x 'nin const * g ile asimptotik olarak ├╝st s─▒n─▒rl─▒d─▒r "anlam─▒na gelir: x'in sonlu de─čerinin alt─▒ndaki her ┼čeyi g├Âz ard─▒ ederek, b├Âyle bir sabit vard─▒r |f(x)| ÔëĄ const * |g(x)| . (Di─čer semboller ┼ču ┼čekildedir: t─▒pk─▒ O ÔëĄ, ╬ę ara├žlar Ôëą gibi. K├╝├ž├╝k harf ├že┼čitleri vard─▒r: o ara├žlar <, ve ¤ë ara├žlar>.) f(x) Ôłł Ăč(g(x)) Her ikisi de f(x) Ôłł O(g(x)) ve f(x) Ôłł ╬ę(g(x)) (g ile ├╝st ve alt s─▒n─▒rland─▒r─▒lm─▒┼č): her zaman const1*g(x) ve aras─▒nda "grup" yalan s├Âyleyecektir const2*g(x) . Yapabilece─činiz en g├╝├žl├╝ asimptotik ifadedir ve kabaca e┼čde─čerdir == . (├ťzg├╝n├╝m, a├ž─▒kl─▒k u─čruna mutlak de─čer sembollerinin s├Âz├╝n├╝ geciktirmeyi se├žtim, a├ž─▒kl─▒k u─čruna; ├Âzellikle bilgisayar bilimleri ba─člam─▒nda olumsuz de─čerler g├Ârmedim ├ž├╝nk├╝).

─░nsanlar = O(...) , belki de daha do─čru 'comp-sci' yaz─▒s─▒ olan ve kullan─▒m─▒ tamamen me┼čru olan; "f = O (...)" okunuyor "f, ... / f, xxx ile ba─čl─▒ ..." d─▒r ve "f'nin asimptotikleri ... olan bir ifadedir" olarak d├╝┼č├╝n├╝l├╝r. Daha titiz kullanmam ├Â─čretildi Ôłł O(...) . Ôłł "bir element" anlam─▒na gelir (daha ├Ânce oldu─ču gibi hala okunur). Bu ├Âzel durumda, O(N┬▓) {gibi ├Â─čeleri i├žerir 2 N┬▓ , 3 N┬▓ , 1/2 N┬▓ , 2 N┬▓ + log(N) , - N┬▓ + N^1.9 , ...} ve sonsuz b├╝y├╝k, ama yine de bir dizi bu.

O ve ╬ę simetrik de─čildir (n = O (n┬▓), fakat n┬▓ O (n) de─čildir), fakat s simetriktir ve (bu ili┼čkilerin t├╝m├╝ ge├ži┼čli ve d├Ân├╝┼čl├╝ oldu─ču i├žin) Ăč bu y├╝zden simetrik ve ge├ži┼čli ve d├Ân├╝┼čl├╝ ve bu nedenle t├╝m fonksiyonlar─▒n k├╝mesini denklik s─▒n─▒flar─▒na b├Âler . Bir denklik s─▒n─▒f─▒, ayn─▒ oldu─čunu d├╝┼č├╝nd├╝─č├╝m├╝z bir dizi ┼čeydir. Yani, akl─▒n─▒za gelebilecek herhangi bir i┼člev verildi─činde, s─▒n─▒f─▒n kanonik / benzersiz bir 'asimptotik temsilcisini' bulabilirsiniz (genel olarak s─▒n─▒r─▒ alarak ... san─▒r─▒m ); t─▒pk─▒ t├╝m tamsay─▒lar─▒ oranlara veya evenslere g├Âre gruplayabildi─činiz gibi, t├╝m fonksiyonlar─▒ x x-ish, log (x) ^ 2-ish, etc ... ile daha k├╝├ž├╝k terimleri yok sayarak grupland─▒rabilirsiniz (ama bazen s─▒k─▒┼č─▒p kalm─▒┼č olabilirsiniz) kendilerine ayr─▒ s─▒n─▒flar olan daha karma┼č─▒k fonksiyonlar).

= Notasyonu daha yayg─▒n biri olabilir ve hatta d├╝nyaca ├╝nl├╝ bilgisayar bilim adamlar─▒ taraf─▒ndan ka─č─▒tlar kullan─▒l─▒r. Ek olarak, ├žo─ču zaman rahat bir ortamda insanlar─▒n ne O(...) zaman demek istediklerini s├Âyleyebilecekleri Ăč(...) ; bu teknik olarak do─črudur ├ž├╝nk├╝ ┼čeyler Ăč(exactlyThis) k├╝mesi bir altk├╝medir O(noGreaterThanThis) ... ve yazmas─▒ daha kolayd─▒r. ;-)


389







EDIT: H─▒zl─▒ not, bu kesinlikle B├╝y├╝k O notasyonunu (bir ├╝st s─▒n─▒rd─▒r) Theta notasyonuyla (hem bir ├╝st hem de alt s─▒n─▒rd─▒r) kar─▒┼čt─▒r─▒r. Deneyimlerime g├Âre bu asl─▒nda akademik olmayan ortamlardaki tart─▒┼čmalar─▒n tipik bir ├Ârne─či. Herhangi bir kar─▒┼č─▒kl─▒ktan dolay─▒ ├Âz├╝r dileriz.

Bir c├╝mlede: ─░┼činizin b├╝y├╝kl├╝─č├╝ artt─▒k├ža, i┼čin tamamlanmas─▒ ne kadar zaman al─▒r?

A├ž─▒k├žas─▒, sadece girdi olarak "boyut" ve ├ž─▒kt─▒ olarak "zaman" kullanmak - haf─▒za kullan─▒m─▒ vb. Hakk─▒nda konu┼čmak istiyorsan─▒z ayn─▒ fikir ge├žerlidir.

─░┼čte size kurutmak istedi─čimiz N Ti┼č├Ârtlerin oldu─ču bir ├Ârnek. Biz edece─čiz varsayal─▒m (yani insan etkile┼čimi ├Ânemsiz) o kuruma pozisyonunda onlar─▒ almak i├žin inan─▒lmaz derecede h─▒zl─▒. Tabii ki ger├žek hayatta durum b├Âyle de─čil ...

  • D─▒┼čar─▒da bir y─▒kama hatt─▒ kullanmak: Sonsuz b├╝y├╝k bir arka bah├ženiz oldu─čunu varsayal─▒m, y─▒kama O (1) zamanla kurur. Ne kadar─▒na sahip olursan─▒z olun, ayn─▒ g├╝ne┼č ve temiz havay─▒ al─▒r, b├Âylece boyut kuruma s├╝resini etkilemez.

  • ├çama┼č─▒r kurutma makinesi kullanarak: her y├╝ke 10 g├Âmlek koyuyorsun, ve bir saat sonra bitiyorlar. (Buradaki ger├žek say─▒lar─▒ yoksay─▒n - bunlar ├Ânemsizdir.) Bu nedenle 50 g├Âmlek kurutma, 10 g├Âmlek kurutman─▒n yakla┼č─▒k 5 kat─▒ s├╝rer .

  • Her ┼čeyi havaland─▒rma dolab─▒na koymak: Her ┼čeyi b├╝y├╝k bir y─▒─č─▒na koyarsak ve genel s─▒cakl─▒─č─▒n yapmas─▒na izin verirsek, orta g├Âmleklerin kurumas─▒ uzun zaman al─▒r. Ayr─▒nt─▒l─▒ olarak tahmin etmek istemem ama bunun en az─▒ndan 0 (N ^ 2) oldu─čundan ┼č├╝pheleniyorum - y─▒kama y├╝k├╝n├╝ artt─▒rd─▒k├ža kuruma s├╝resi daha h─▒zl─▒ artar.

"B├╝y├╝k O" g├Âsterimde ├Ânemli ├Âzelliklerinden biri, tam o gelmez daha h─▒zl─▒ bir boyut i├žin olacak algoritma demek. Bir ├žiftler dizisine (string, integer) kar┼č─▒ bir hastable (string key, integer value) al─▒n. Bir dizgeye dayanarak, karma tablodaki bir anahtar─▒ veya dizideki bir ├Â─čeyi bulmak daha m─▒ h─▒zl─▒d─▒r? (yani, dizi i├žin, "dizge par├žas─▒n─▒n verilen anahtarla e┼čle┼čti─či ilk eleman─▒ bulun.") Hashtables'ler genellikle itfa edilir (~ = "ortalamada") O (1) - ayarland─▒ktan sonra, yakla┼č─▒k olarak Ayn─▒ zamanda 100.000 giri┼č tablosunda, 1.000.000 giri┼č tablosundaki bir giri┼či bulmak i├žin. Dizideki bir ├Â─čeyi bulmak (indeks yerine i├žeri─če ba─čl─▒ olarak) do─črusald─▒r, yani O (N) - ortalama olarak girdilerin yar─▒s─▒na bakman─▒z gerekir.

Bu, aramalar i├žin bir diziden daha h─▒zl─▒ bir tablo yarat─▒r m─▒? ┼×art de─čil. ├çok k├╝├ž├╝k bir giri┼č koleksiyonunuz varsa, bir dizi daha h─▒zl─▒ olabilir - yaln─▒zca bakt─▒─č─▒n─▒z─▒n kodunu hesaplamak i├žin gereken s├╝re i├žinde t├╝m karakter dizilerini kontrol edebilirsiniz. Ancak, veri seti b├╝y├╝d├╝k├že, karma tablo sonunda diziyi ge├žecektir.


242







B├╝y├╝k O, girdiler b├╝y├╝k oldu─čunda bir i┼člevin b├╝y├╝me davran─▒┼č─▒, ├Ârne─čin bir program─▒n ├žal─▒┼čma zaman─▒ gibi ├╝st bir s─▒n─▒r─▒ tan─▒mlar.

├ľrnekler:

  • O (n): Giri┼č boyutunu iki kat─▒na ├ž─▒kar─▒rsam ├žal─▒┼čma s├╝resi iki kat─▒na ├ž─▒kar.

  • O (n 2 ): Girdi boyutu ├žal─▒┼čma zaman─▒n─▒n d├Ârt kat─▒n─▒ iki kat─▒na ├ž─▒kar─▒rsa

  • O (log n): Girdi boyutu ikiye katlan─▒rsa, ├žal─▒┼čma s├╝resi bir kat artar

  • O (2 n ): Girdi boyutu bir artarsa ÔÇőÔÇő├žal─▒┼čma s├╝resi iki kat artar

Giri┼č boyutu genellikle giri┼či temsil etmek i├žin gereken bit cinsinden aland─▒r.


124







Big O notasyonu en ├žok programc─▒lar taraf─▒ndan bir hesaplaman─▒n (algoritman─▒n) girdi k├╝mesinin boyutunun bir fonksiyonu olarak ne kadar s├╝rede tamamlanaca─č─▒n─▒n yakla┼č─▒k bir ├Âl├ž├╝s├╝ olarak kullan─▒l─▒r.

B├╝y├╝k O, giri┼č say─▒s─▒ artt─▒k├ža iki algoritman─▒n ne kadar iyi ├Âl├žeklenece─čini kar┼č─▒la┼čt─▒rmak i├žin kullan─▒┼čl─▒d─▒r.

Daha do─črusu Big O notasyonu , bir fonksiyonun asimptotik davran─▒┼č─▒n─▒ ifade etmek i├žin kullan─▒l─▒r. Bu, i┼člevin sonsuzlu─ča yakla┼č─▒rken nas─▒l davrand─▒─č─▒ anlam─▒na gelir.

├ço─ču durumda bir algoritman─▒n "O" si a┼ča─č─▒daki durumlardan birine d├╝┼čecektir:

  • O (1) - Tamamlanma s├╝resi, ayarlanan giri┼čin boyutuna bak─▒lmaks─▒z─▒n ayn─▒d─▒r. Bir ├Ârnek, bir dizi ├Â─česine indeksle eri┼čmektir.
  • O (Log N) - Tamamlanma s├╝resi log2 (n) ile uyumlu olarak kabaca artar. ├ľrne─čin, 1024 madde 32 maddeden iki kat daha uzun s├╝rer, ├ž├╝nk├╝ Log2 (1024) = 10 ve Log2 (32) = 5'tir. ├ľrnek bir ikili arama a─čac─▒nda (BST) bir madde bulmakt─▒r .
  • O (N) - Giri┼č k├╝mesinin boyutuyla do─črusal olarak ├Âl├žeklenen tamamlanma zaman─▒. Ba┼čka bir deyi┼čle, giri┼č k├╝mesindeki ├Â─čelerin say─▒s─▒n─▒ iki kat─▒na ├ž─▒kar─▒rsan─▒z, algoritma kabaca iki kat daha uzun s├╝rer. Bir ├Ârnek, ba─člant─▒l─▒ bir listedeki ├Â─čelerin say─▒s─▒n─▒ say─▒yor.
  • O (N Log N) - Tamamlanma s├╝resi, Log2 (N) sonucunun ├žarp─▒ say─▒s─▒ kadar artar. Buna bir ├Ârnek y─▒─č─▒n s─▒ralama ve h─▒zl─▒ s─▒ralamad─▒r .
  • O (N ^ 2) - Tamamlanma s├╝resi yakla┼č─▒k olarak ├Â─čelerin say─▒s─▒n─▒n karesine e┼čittir. Buna bir ├Ârnek kabarc─▒k s─▒ralamad─▒r .
  • O (N!) - Tamamlanma s├╝resi giri┼č setinin fakt├Âr├╝d├╝r. Buna bir ├Ârnek seyahat eden sat─▒c─▒ problemi kaba kuvvet ├ž├Âz├╝m├╝d├╝r .

B├╝y├╝k O, giri┼č boyutu sonsuzlu─ča do─čru artt─▒k├ža, bir fonksiyonun b├╝y├╝me e─črisine anlaml─▒ bir ┼čekilde katk─▒da bulunmayan fakt├Ârleri g├Ârmezden gelir. Bu, fonksiyona eklenen veya ├žarp─▒lan sabitlerin basit├že yok say─▒ld─▒─č─▒ anlam─▒na gelir.


103







B├╝y├╝k O, kendinizi ortak bir ┼čekilde ÔÇťifade etmeninÔÇŁ bir yoludur, ÔÇťKodumu ├žal─▒┼čt─▒rmak i├žin ne kadar zaman / alan gerekiyor?ÔÇŁ.

S─▒k s─▒k O (n), O (n 2 ), O (nlogn) ve benzerlerini g├Ârebilirsiniz. Bunlar─▒n hepsi g├Âstermenin yoludur; Bir algoritma nas─▒l de─či┼čir?

O (n), B├╝y├╝k O'nun n oldu─ču anlam─▒na gelir ve ┼čimdi ÔÇťN nedir !?ÔÇŁ diyebilirsiniz. Eh "n" elementlerin miktar─▒d─▒r. Dizi i├žinde bir ├ľ─če aramak istedi─činizde g├Âr├╝nt├╝leme. Her bir ├Â─čeye ve "Do─čru ├Â─če / ├Â─če misiniz?" Olarak bakman─▒z gerekir. En k├Ât├╝ durumda, madde son dizinde, yani listedeki ├Â─čeler kadar uzun s├╝rd├╝─č├╝ anlam─▒na geliyor, bu nedenle genel olmas─▒ i├žin "aa, n, adil bir de─čer miktar─▒!" diyoruz. .

├ľyleyse "n 2 " nin ne anlama geldi─čini anlayabilirsiniz , ancak daha da spesifik olmak gerekirse, s─▒ralama algoritmalar─▒n─▒n en basitine sahip oldu─čunu d├╝┼č├╝nd├╝─č├╝n├╝z bir oyunla oynayabilirsiniz; BubbleSort. Bu algoritman─▒n her ├Â─če i├žin t├╝m listeye bakmas─▒ gerekir.

Listem

  1. 1
  2. 6
  3. 3

Buradaki ak─▒┼č ┼č├Âyle olurdu:

  • 1 ve 6'y─▒ kar┼č─▒la┼čt─▒r─▒n, hangisi daha b├╝y├╝k? Ok 6 do─čru pozisyonda, ilerliyor!
  • 6 ve 3'├╝ kar┼č─▒la┼čt─▒r─▒n, oh, 3 daha az! Hadi devam edelim, tamam liste de─či┼čti, ┼čimdi ba┼čtan ba┼člamam─▒z gerek!

Bunun sebebi O 2 ├ž├╝nk├╝ listedeki t├╝m maddelere bakman─▒z gerekiyor "n" maddeleri var. Her ├Â─če i├žin, t├╝m ├Â─čelere bir kez daha bakars─▒n─▒z, kar┼č─▒la┼čt─▒rmak i├žin, bu da "n" dir, bu nedenle her ├Â─če i├žin, n * n = n 2 anlam─▒na gelen "n" kez bakars─▒n─▒z. 2

Umar─▒m bu istedi─činiz kadar basittir.

Ancak unutmay─▒n, B├╝y├╝k O sadece zaman ve mek├ón bi├žiminde kendinizi ifade etmenin bir yoludur.


81







Big O, bir algoritman─▒n temel ├Âl├žeklendirme niteli─čini tan─▒mlar.

B├╝y├╝k O'nun size verilen bir algoritmadan bahsetmedi─či bir├žok bilgi var. Kemi─či keser ve sadece bir algoritman─▒n ├Âl├žeklendirme do─čas─▒ hakk─▒nda, ├Âzellikle bir algoritman─▒n kaynak kullan─▒m─▒n─▒n (d├╝┼č├╝nme zaman─▒ veya haf─▒zas─▒n─▒) "giri┼č b├╝y├╝kl├╝─č├╝ne" cevap olarak nas─▒l ├Âl├žeklendirdi─či hakk─▒nda bilgi verir.

Bir buhar motoru ve bir roket aras─▒ndaki fark─▒ d├╝┼č├╝n├╝n. Ayn─▒ ┼čeyin sadece farkl─▒ ├že┼čitleri de─čiller (diyelim, Prius motoru vs Lamborghini motoru gibi), ancak ├Âz├╝nde ├žarp─▒c─▒ bi├žimde farkl─▒ tahrik sistemleridirler. Bir buhar motoru, bir oyuncak roketten daha h─▒zl─▒ olabilir, fakat hi├žbir y├Âr├╝nge f─▒rlatma arac─▒n─▒n h─▒zlar─▒na ula┼čmak i├žin hi├žbir buhar pistonu motoru m├╝mk├╝n olmayacakt─▒r. Bunun nedeni, bu sistemlerin belirli bir h─▒za ("giri┼č boyutu") ula┼čmak i├žin gereken yak─▒t ("kaynak kullan─▒m─▒") ile ilgili olarak farkl─▒ ├Âl├žeklendirme ├Âzelliklerine sahip olmalar─▒d─▒r.

Bu neden bu kadar ├Ânemli? ├ç├╝nk├╝ yaz─▒l─▒m, trilyona kadar olan fakt├Ârlere g├Âre farkl─▒l─▒klar g├Âsterebilecek problemlerle ilgileniyor. Bunu bir anl─▒─č─▒na d├╝┼č├╝n├╝n. Ay'a gitmek i├žin gereken h─▒z ile insan y├╝r├╝me h─▒z─▒ aras─▒ndaki oran 10.000: 1'den azd─▒r ve giri┼č boyutlar─▒ yaz─▒l─▒m─▒ndaki y├╝zdeye g├Âre kesinlikle ├žok k├╝├ž├╝kt├╝r. Yaz─▒l─▒m, girdi boyutlar─▒nda astronomik bir aral─▒kla kar┼č─▒la┼čabilece─či i├žin, bir algoritman─▒n Big O karma┼č─▒kl─▒─č─▒, temel ├Âl├žeklendirme niteli─či, herhangi bir uygulama detay─▒n─▒ a┼čma potansiyeli vard─▒r.

Kurall─▒ s─▒ralama ├Ârne─čini d├╝┼č├╝n├╝n. Kabarc─▒k s─▒ralama O (n 2 ) olurken, birle┼čtirme s─▒ralama O (n log n) olur. Diyelim ki iki s─▒ralama uygulaman─▒z oldu─čunu, kabarc─▒k s─▒ralama kullanan uygulama A'y─▒ ve birle┼čtirme s─▒ralama kullanan uygulama B'yi diyelim ve diyelim ki yakla┼č─▒k 30 eleman─▒n giri┼č boyutlar─▒ i├žin uygulama A'n─▒n s─▒ralamadaki uygulama B'den 1000 kat daha h─▒zl─▒ oldu─čunu varsayal─▒m. E─čer 30'dan fazla elementi asla s─▒ralamak zorunda kalmazsan─▒z, bu girdi boyutlar─▒nda ├žok daha h─▒zl─▒ oldu─ču i├žin A uygulamas─▒n─▒ tercih etmeniz gerekti─či a├ž─▒kt─▒r. Bununla birlikte, on milyon ├Â─čeyi s─▒ralaman─▒z gerekebilece─čini fark ederseniz, bekledi─činiz ┼čey, B uygulamas─▒n─▒n, bu durumda, her bir algoritman─▒n tamamen ├Âl├žeklenmesi nedeniyle, asl─▒nda A uygulamas─▒ndan binlerce kat daha h─▒zl─▒ sonu├žlanmas─▒d─▒r.


54







─░┼čte, Big-O'nun ortak ├že┼čitlerini a├ž─▒klarken, kullanma e─čiliminde oldu─čum en sade ─░ngiliz el├žisi.

Her durumda, listede daha d├╝┼č├╝k olanlara daha y├╝ksek olan algoritmalar─▒ tercih et. Bununla birlikte, daha pahal─▒ bir karma┼č─▒kl─▒k s─▒n─▒f─▒na ge├žmenin maliyeti ├Ânemli ├Âl├ž├╝de de─či┼čmektedir.

O (1):

B├╝y├╝me yok. Sorunun ne kadar b├╝y├╝k oldu─čuna bak─▒lmaks─▒z─▒n, ayn─▒ s├╝rede ├ž├Âzebilirsiniz. Bu, yay─▒n aral─▒─č─▒n─▒n i├žinde yer alan ki┼či say─▒s─▒na bak─▒lmaks─▒z─▒n, belirli bir mesafeden yay─▒n yapmak i├žin ayn─▒ miktarda enerji harcad─▒─č─▒ yay─▒n i├žin bir nebzedir.

O (log n ):

Bu karma┼č─▒kl─▒k, biraz daha k├Ât├╝ olmas─▒ d─▒┼č─▒nda, O (1) ile ayn─▒d─▒r. T├╝m pratik ama├žlar i├žin, bunu ├žok b├╝y├╝k bir sabit ├Âl├žeklendirme olarak d├╝┼č├╝nebilirsiniz. ─░┼čin 1 bin ile 1 milyar aras─▒nda i┼členmesi aras─▒ndaki fark sadece alt─▒ fakt├Ârd├╝r.

O ( n ):

Sorunu ├ž├Âzmenin maliyeti, sorunun boyutu ile orant─▒l─▒d─▒r. Sorununuzun boyutu iki kat─▒na ├ž─▒karsa, ├ž├Âz├╝m├╝n maliyeti iki kat─▒na ├ž─▒kar. ├ço─ču sorunun bilgisayara bir ┼čekilde taranmas─▒ gerekti─činden, veri giri┼či, disk okur veya a─č trafi─či gibi, bu genellikle uygun bir ├Âl├žeklendirme fakt├Âr├╝d├╝r.

O ( n log n ):

Bu karma┼č─▒kl─▒k, O ( n ) ' ye ├žok benzer . T├╝m pratik ama├žlar i├žin, ikisi e┼čde─čerdir. Bu karma┼č─▒kl─▒k d├╝zeyi genellikle hala ├Âl├žeklenebilir olarak kabul edilir. Varsay─▒mlar─▒ ince ayarlayarak, baz─▒ O ( n log n ) algoritmalar─▒ O ( n ) algoritmalar─▒na d├Ân├╝┼čt├╝r├╝lebilir. ├ľrne─čin, tu┼člar─▒n boyutunu s─▒n─▒rlamak, O ( n log n ) ' den O ( n )' ye s─▒ralama i┼člemini azalt─▒r .

O ( n 2 ):

N bir karenin kenar─▒n─▒n uzunlu─ču oldu─ču bir kare olarak b├╝y├╝r . Bu, a─čdaki herkesin a─čdaki herkesi tan─▒yabilece─či "a─č etkisi" ile ayn─▒ b├╝y├╝me oran─▒d─▒r. B├╝y├╝me pahal─▒d─▒r. ├ço─ču ├Âl├žeklenebilir ├ž├Âz├╝m, ├Ânemli jimnastik yapmadan bu karma┼č─▒kl─▒k seviyesindeki algoritmalar─▒ kullanamaz. Bu genellikle di─čer t├╝m polinom karma┼č─▒kl─▒klar─▒ i├žin de ge├žerlidir - O ( n k ) -.

0 (2 n ):

├ľl├žek yapmaz. ├ľnemsiz boyutta bir problemi ├ž├Âzme umudunuz yoktur. Ka├ž─▒n─▒lmas─▒ gereken ┼čeyleri bilmek ve uzmanlar─▒n O ( n k ) i├žindeki yakla┼č─▒k algoritmalar─▒ bulmas─▒ i├žin kullan─▒┼čl─▒d─▒r .


39







B├╝y├╝k O, bir algoritman─▒n, giri┼činin boyutuna g├Âre ne kadar zaman / alan kulland─▒─č─▒n─▒n bir ├Âl├ž├╝s├╝d├╝r.

Bir algoritma O (n) ise, zaman / alan giri┼či ile ayn─▒ oranda artacakt─▒r.

Bir algoritma O (n 2 ) ise, zaman / bo┼čluk giri┼č karesi oran─▒nda artar.

ve bunun gibi.


36







Yaz─▒l─▒m programlar─▒n─▒n h─▒z─▒n─▒ ├Âl├žmek ├žok zordur ve denedi─čimizde cevaplar ├žok karma┼č─▒k olabilir ve istisnalar ve ├Âzel durumlar ile doldurulabilir. Bu b├╝y├╝k bir sorundur, ├ž├╝nk├╝ bu istisnalar ve ├Âzel durumlar, hangisinin ÔÇťen h─▒zl─▒ÔÇŁ oldu─čunu bulmak i├žin iki farkl─▒ program─▒ birbiriyle kar┼č─▒la┼čt─▒rmak istedi─čimizde dikkat da─č─▒t─▒c─▒ ve yarars─▒zd─▒r.

B├╝t├╝n bu yarars─▒z karma┼č─▒kl─▒─č─▒n bir sonucu olarak, insanlar yaz─▒l─▒m programlar─▒n─▒n h─▒z─▒n─▒ m├╝mk├╝n olan en k├╝├ž├╝k ve en az karma┼č─▒k (matematiksel) ifadeleri kullanarak tan─▒mlamaya ├žal─▒┼č─▒rlar. Bu ifadeler ├žok kaba yakla┼č─▒mlard─▒r: Biraz ┼čansla, bir yaz─▒l─▒m─▒n h─▒zl─▒ veya yava┼č olup olmad─▒─č─▒n─▒n "├Âz├╝n├╝" yakalayacaklard─▒r.

Yakla┼č─▒m olduklar─▒ndan, ifadede "O" harfini (B├╝y├╝k Oh) ÔÇőÔÇőkullan─▒yoruz, okuyucuya b├╝y├╝k bir basitle┼čtirme yapt─▒─č─▒m─▒z─▒n sinyalini vermek i├žin. (Ve kimsenin yanl─▒┼čl─▒kla ifadenin herhangi bir ┼čekilde do─čru oldu─čunu d├╝┼č├╝nmedi─činden emin olmak i├žin).

"Oh" s─▒ras─▒n─▒ "s─▒ras─▒na" veya "yakla┼č─▒k olarak" okursan─▒z, ├žok fazla yanl─▒┼č gitmezsiniz. (Big-Oh'un se├žiminin mizah giri┼čimi olabilece─čini d├╝┼č├╝n├╝yorum).

Bu "Big-Oh" ifadelerinin yapmay─▒ denedi─či tek ┼čey, yaz─▒l─▒m─▒n i┼člemesi gereken veri miktar─▒n─▒ artt─▒rd─▒k├ža, yaz─▒l─▒m─▒n ne kadar yava┼člad─▒─č─▒n─▒ a├ž─▒klamakt─▒r. ─░┼členmesi gereken veri miktar─▒n─▒ ikiye katlarsak, yaz─▒l─▒m─▒n ├žal─▒┼čmas─▒n─▒ tamamlamak i├žin iki kez daha ihtiyac─▒ olur mu? 10 kere mi? Uygulamada, kar┼č─▒la┼čaca─č─▒n─▒z ve endi┼čelenmeniz gereken ├žok s─▒n─▒rl─▒ say─▒da b├╝y├╝k Oh ifadesi vard─▒r:

─░yi:

  • O(1) Sabit : Girdi ne kadar b├╝y├╝k olursa olsun program─▒n ├žal─▒┼čmas─▒ ayn─▒ zaman al─▒r.
  • O(log n) Logaritmik : Program ├žal─▒┼čma zaman─▒, giri┼čin b├╝y├╝kl├╝─č├╝nde b├╝y├╝k art─▒┼člarla bile, sadece yava┼č├ža artar.

K├Ât├╝:

  • O(n) Do─črusal : Program─▒n ├žal─▒┼čma s├╝resi, giri┼čin boyutuyla orant─▒l─▒ olarak artar.
  • O(n^k) Polinom : - ─░┼člem s├╝resi daha h─▒zl─▒ ve daha h─▒zl─▒ b├╝y├╝r - polinom i┼člevi olarak - giri┼čin boyutu artt─▒k├ža.

... ve ├žirkin:

  • O(k^n) ├ťstel Program─▒n ├žal─▒┼čma s├╝resi, problemin boyutunda ─▒l─▒ml─▒ art─▒┼člarla bile ├žok h─▒zl─▒ bir ┼čekilde artar - yaln─▒zca k├╝├ž├╝k veri k├╝melerini ├╝stel algoritmalar ile i┼člemek pratiktir.
  • O(n!) Fakt├Âriyel Program─▒n ├žal─▒┼čma s├╝resi, en k├╝├ž├╝k ve en ├Ânemsiz g├Âr├╝nen veri k├╝meleri d─▒┼č─▒nda bir ┼čeyi beklemekten daha uzun olacakt─▒r.

32







B├╝y├╝k OÔÇÖnun basit bir ─░ngilizce a├ž─▒klamas─▒ nedir? M├╝mk├╝n oldu─čunca basit ve basit matematik ile resmi tan─▒m─▒.

Big-O Notasyonu ─░htiyac─▒n─▒n Sade Bir ─░ngilizcesi :

Programlad─▒─č─▒m─▒z zaman, bir sorunu ├ž├Âzmeye ├žal─▒┼č─▒yoruz. Kodlad─▒─č─▒m─▒z ┼čeye algoritma denir. Big O notasyonu, algoritmalar─▒m─▒z─▒n en k├Ât├╝ durum performans─▒n─▒ standart bir ┼čekilde kar┼č─▒la┼čt─▒rmam─▒z─▒ sa─člar. Donan─▒m ├Âzellikleri zaman i├žinde de─či┼čiklik g├Âsterir ve donan─▒mdaki iyile┼čtirmeler bir algoritman─▒n ├žal─▒┼čmas─▒ i├žin gereken s├╝reyi azaltabilir. Fakat donan─▒m─▒ de─či┼čtirmek, algoritmam─▒z─▒n hala ayn─▒ olmas─▒ nedeniyle algoritmam─▒z─▒n zaman i├žinde daha iyi veya daha iyi oldu─ču anlam─▒na gelmez. Bu nedenle, farkl─▒ algoritmalar─▒ kar┼č─▒la┼čt─▒rmam─▒za izin vermek, birinin daha iyi olup olmad─▒─č─▒n─▒ belirlemek i├žin B├╝y├╝k O notasyonu kullan─▒yoruz.

B├╝y├╝k O Notasyonu Nedir : Basit Bir ─░ngilizce A├ž─▒klama :

T├╝m algoritmalar ayn─▒ s├╝rede ├žal─▒┼čmaz ve giri┼čte n olarak adland─▒rd─▒─č─▒m─▒z ├Â─če say─▒s─▒na ba─čl─▒ olarak de─či┼čebilir . Buna dayanarak, en k├Ât├╝ durum analizini veya n'in b├╝y├╝d├╝k├že ├žal─▒┼čma zaman─▒n─▒n ├╝st s─▒n─▒r─▒n─▒ d├╝┼č├╝nd├╝─č├╝m├╝z├╝ d├╝┼č├╝n├╝yoruz . Biz fark─▒nda olmal─▒d─▒r n B├╝y├╝k O notasyonu bir├žok ona ba┼čvuru nedeni vard─▒r.


32







Basit ve basit bir cevap olabilir:

B├╝y├╝k O, bu algoritma i├žin olas─▒ en k├Ât├╝ zaman / alan─▒ temsil eder. Algoritma asla bu s─▒n─▒r─▒n ├╝st├╝nde daha fazla yer / zaman almayacakt─▒r. B├╝y├╝k O, a┼č─▒r─▒ durumda zaman / mekan karma┼č─▒kl─▒─č─▒n─▒ temsil eder.


28







Tamam, 2 sentim.

Big-O, program taraf─▒ndan t├╝ketilen kayna─č─▒n art─▒┼č oran─▒ , wrt problemi-case-size

Kaynak: Toplam CPU zaman─▒ olabilir, maksimum RAM alan─▒ olabilir. Varsay─▒lan olarak CPU zaman─▒d─▒r.

Sorunun "Toplam─▒ bul" deyin,

 int Sum(int*arr,int size){
      int sum=0;
      while(size-->0) 
         sum+=arr[size]; 

      return sum;
}
 

sorun ├Ârne─či = {5,10,15} ==> sorun ├Ârne─či boyutu = 3, d├Âng├╝ i├ži yineleme = 3

sorun ├Ârne─či = {5,10,15,20,25} ==> sorun ├Ârne─či boyutu = 5 d├Âng├╝ i├žinde yineleme = 5

"N" boyutunun girilmesi i├žin program dizideki "n" yinelemelerin h─▒z─▒nda b├╝y├╝yor. Dolay─▒s─▒yla, B├╝y├╝k O, O (n) olarak ifade edilen N'dir.

Sorunun ÔÇťKombinasyonu BulÔÇŁ oldu─čunu s├Âyleyin,

     void Combination(int*arr,int size)
    { int outer=size,inner=size;
      while(outer -->0) {
        inner=size;
        while(inner -->0)
          cout<<arr[outer]<<"-"<<arr[inner]<<endl;
      }
    }
 

sorun ├Ârne─či = {5,10,15} ==> sorun ├Ârne─či boyutu = 3, toplam yineleme = 3 * 3 = 9

sorun ├Ârne─či = {5,10,15,20,25} ==> sorun ├Ârne─či boyutu = 5, toplam yineleme = 5 * 5 = 25

"N" boyutu giri┼či i├žin program, dizideki "n * n" yinelemelerin h─▒z─▒nda b├╝y├╝yor. Bu nedenle b├╝y├╝k O, N 2 O (n olarak ifade 2 )


28







B├╝y├╝k O notasyonu, bir algoritman─▒n ├╝st s─▒n─▒r─▒n─▒ uzay veya ├žal─▒┼čma s├╝resi a├ž─▒s─▒ndan tan─▒mlaman─▒n bir yoludur. N, problemdeki elementlerin say─▒s─▒d─▒r (yani bir dizinin b├╝y├╝kl├╝─č├╝, bir a─ča├žtaki d├╝─č├╝mlerin say─▒s─▒, vb.) ├çal─▒┼čma zaman─▒n─▒ n b├╝y├╝d├╝k├že tan─▒mlamakla ilgileniyoruz.

Baz─▒ algoritmalar─▒n O (f (n)) oldu─čunu s├Âyledi─čimizde, o algoritman─▒n ├žal─▒┼čma zaman─▒n─▒n (veya gerekli alan─▒n) her zaman f (n) sabit zamanlar─▒ndan daha d├╝┼č├╝k oldu─čunu s├Âyl├╝yoruz.

─░kili araman─▒n ├žal─▒┼čma s├╝resi O (logn) oldu─čunu s├Âylemek, g├╝nl├╝k (n) 'i ├žarparak alabilece─činiz baz─▒ c sabitlerinin var oldu─čunu, bunun her zaman ikili araman─▒n ├žal─▒┼čma s├╝resinden daha b├╝y├╝k olaca─č─▒n─▒ s├Âylemek anlam─▒na gelir. Bu durumda, her zaman baz─▒ sabit log (n) kar┼č─▒la┼čt─▒rma fakt├Ârlerine sahip olacaks─▒n─▒z.

Ba┼čka bir deyi┼čle, g (n) 'in algoritman─▒z─▒n ├žal─▒┼čma s├╝resi oldu─ču, n (k) oldu─čunda, g (n) = g (n) = g (n) <= c * f (n) oldu─čunda c ve k baz─▒ sabitler.


26







ÔÇť B├╝y├╝k O'nun basit bir ─░ngilizce a├ž─▒klamas─▒ nedir? M├╝mk├╝n oldu─čunca az basit tan─▒m ve basit matematik. ÔÇŁ

B├Âyle g├╝zel, basit ve k─▒sa bir soru, en az─▒ndan bir ├Â─črencinin ders s─▒ras─▒nda alabilece─či gibi e┼čit derecede k─▒sa bir cevab─▒ hak ediyor gibi g├Âr├╝nmektedir.

B├╝y├╝k O g├Âsterimi, bir algoritman─▒n yaln─▒zca girdi verisi miktar─▒ ** cinsinden ne kadar s├╝re * i├žinde ├žal─▒┼čabilece─čini s├Âyler .

(Harika, i├žinde * birimi i├žermeyen zaman anlam─▒nda!)
(** insanlar, ├ž├╝nk├╝ ├Ânemli olan her zaman daha ├žok istiyorum , ister canl─▒ bug├╝n veya yar─▒n)

B├╝y├╝k O notasyonu i├žin bu kadar harika olan ne varsa?

  • Pratik olarak konu┼čursak, Big O analizi ├žok faydal─▒ ve ├Ânemlidir ├ž├╝nk├╝ Big O oda─č─▒ algoritman─▒n kendi karma┼č─▒kl─▒─č─▒na odaklar ve sadece orant─▒l─▒l─▒k sabiti olan her ┼čeyi g├Ârmezden gelir - bir JavaScript motoru, bir CPU h─▒z─▒, ─░nternet ba─člant─▒n─▒z ve h─▒zla geli┼čen bu ┼čeyler Model T kadar g├╝l├╝n├ž derecede modas─▒ ge├žmi┼č oldu . B├╝y├╝k O, yaln─▒zca mevcut veya gelecekte ya┼čayan insanlara e┼čit derecede ├Ânemli olan ┼čekilde performansa odaklan─▒r.

  • Big O notasyonu ayr─▒ca, t├╝m iyi programc─▒lar─▒ d├╝┼č├╝nmeye ve hayal kurmaya devam etmek i├žin ilham veren, bilgisayar programlama / m├╝hendisli─čin en ├Ânemli prensibine do─črudan ─▒┼č─▒k tutar: teknolojinin yava┼č ilerleyi┼činin ├Âtesinde sonu├žlar elde etmenin tek yolu daha iyi bir icat etmektir. algoritmas─▒ .


24







Algoritma ├Ârne─či (Java):

 // given a list of integers L, and an integer K
public boolean simple_search(List<Integer> L, Integer K)
{
    // for each integer i in list L
    for (Integer i : L)
    {
        // if i is equal to K
        if (i == K)
        {
            return true;
        }
    }

    return false;
}
 

Algoritma a├ž─▒klamas─▒:

  • Bu algoritma, bir liste, bir ├Â─čeye g├Âre arama, bir anahtar ar─▒yor,

  • Listedeki her ├Â─čeyi yineleme, e─čer anahtarsa, True de─čerini d├Ând├╝r,

  • E─čer d├Âng├╝ anahtar─▒ bulmadan bitmi┼čse, False d├Ând├╝r├╝n.

Big-O notasyonu Karma┼č─▒kl─▒k ├╝st s─▒n─▒r─▒n─▒ temsil eder (Zaman, Uzay, ..)

Zaman Karma┼č─▒kl─▒─č─▒ndaki Big-O'yu bulmak i├žin:

  • En k├Ât├╝ durumun ne kadar zaman alaca─č─▒n─▒ (giri┼č boyutuyla ilgili olarak) hesaplay─▒n:

  • En K├Ât├╝ Durum: Anahtar listede yok.

  • Zaman (En K├Ât├╝ Durum) = 4n + 1

  • Zaman: O (4n + 1) = 0 (n) | Big-OÔÇÖda sabitler ihmal edilir

  • O (n) ~ Do─črusal

Best-Case'in karma┼č─▒kl─▒─č─▒n─▒ temsil eden Big-Omega da var:

  • En ─░yi Durum: Anahtar ilk ├Â─čedir.

  • Zaman (En ─░yi Durum) = 4

  • Zaman: ╬ę (4) = 0 (1) ~ Anl─▒k \ Sabit


22







B├╝y├╝k o

f (x) = 0 ( g (x)), x bir (├Ârne─čin, a = + Ôł×) oldu─čunda, ┼č├Âyle bir i┼člev k anlam─▒na gelir :

  1. f (x) = k (x) g (x)

  2. k, bir mahallenin s─▒n─▒rlar─▒na ba─član─▒r (e─čer a = + Ôł× ise, bu, her x> N, | k (x) | <M i├žin oldu─ču gibi, N ve M say─▒lar─▒ oldu─ču anlam─▒na gelir .

Ba┼čka bir deyi┼čle, d├╝z ─░ngilizce olarak: f (x) = 0 ( g (x)), x Ôćĺ a, a'n─▒n bir mahallesinde, f'nin g ve baz─▒ s─▒n─▒rl─▒ fonksiyonlar─▒n ├╝r├╝n├╝nde par├žaland─▒─č─▒ anlam─▒na gelir .

K├╝├ž├╝k o

Bu arada, burada k├╝├ž├╝k o tan─▒m─▒ kar┼č─▒la┼čt─▒rmak i├žindir.

f (x) = o ( g (x)), x, bir k i┼člevinin oldu─ču anlam─▒na gelir:

  1. f (x) = k (x) g (x)

  2. x (a) konumuna geldi─činde k (x) 0 olur.

├ľrnekler

  • x Ôćĺ 0 oldu─čunda sin x = O (x).

  • x = + Ôł× oldu─čunda sin x = O (1),

  • x 2 + x = (x) X, Ôćĺ 0,

  • x 2 + x = 0 (x 2 ) x Ôćĺ + Ôł×,

  • ln (x) = o (x) = 0 (x) x Ôćĺ + Ôł× oldu─čunda.

Dikkat! "=" E┼čittir i┼čaretli g├Âsterimde "sahte e┼čitlik" kullan─▒l─▒r: o (g (x)) = O (g (x)) oldu─ču do─čru, ancak yanl─▒┼č (O (g (x)) = o (g) oldu─ču do─čru (x)). Benzer ┼čekilde, x Ôćĺ + Ôł× yazarken "ln (x) = o (x)" yaz─▒l─▒r, ancak "o (x) = ln (x)" form├╝l├╝ bir anlam ifade etmez.

Daha fazla ├Ârnek

  • O (1) = O (n) = O (n 2 ), n Ôćĺ + Ôł× oldu─čunda (ancak tersi de─čil, e┼čitlik "sahtedir"),

  • O (n) + 0 (n 2 ) = 0 (n 2 ), n Ôćĺ + Ôł× iken

  • O (O (n 2 )) = O (n 2 ), n Ôćĺ + Ôł× iken

  • O (n 2 ) O (n 3 ) = O (n 5 ), n + Ôćĺ Ôł×


─░┼čte Vikipedi maddesi: https://en.wikipedia.org/wiki/Big_O_notation


18







B├╝y├╝k O notasyonu, "n" olarak adland─▒rd─▒─č─▒m─▒z, rastgele say─▒da girdi parametresi verildi─činde bir algoritman─▒n ne kadar h─▒zl─▒ ├žal─▒┼čaca─č─▒n─▒ a├ž─▒klaman─▒n bir yoludur. Bilgisayar biliminde kullan─▒┼čl─▒d─▒r, ├ž├╝nk├╝ farkl─▒ makineler farkl─▒ h─▒zlarda ├žal─▒┼č─▒r ve bir algoritman─▒n 5 saniye s├╝rd├╝─č├╝n├╝ s├Âylemek size pek s├Âylemez ├ž├╝nk├╝ 4,5 GHz octo ├žekirdekli i┼člemcili bir sistemi ├žal─▒┼čt─▒r─▒yor olabilirsiniz. algoritmadan ba─č─▒ms─▒z olarak daha uzun s├╝rebilen, 15 ya┼č─▒nda, 800 Mhz'lik bir sistem. Dolay─▒s─▒yla bir algoritman─▒n zaman a├ž─▒s─▒ndan ne kadar h─▒zl─▒ ├žal─▒┼čt─▒─č─▒n─▒ belirlemek yerine, giri┼č parametresi say─▒s─▒ veya "n" cinsinden ne kadar h─▒zl─▒ ├žal─▒┼čt─▒─č─▒n─▒ s├Âyleriz. Algoritmalar─▒ bu ┼čekilde tan─▒mlayarak, bilgisayar─▒n h─▒z─▒n─▒ hesaba katmak zorunda kalmadan algoritmalar─▒n h─▒zlar─▒n─▒ kar┼č─▒la┼čt─▒rabiliriz.


18







Konuya daha fazla katk─▒da bulundu─čumdan emin de─čilim ama yine de payla┼čaca─č─▒m─▒ d├╝┼č├╝nd├╝m: Bir keresinde bu blog postas─▒n─▒ B├╝y├╝k O hakk─▒nda baz─▒ olduk├ža basit (ancak temel) a├ž─▒klamalar ve ├Ârnekler i├žin buldum :

├ľrneklerle, bu basit temelleri kaplumba─ča kabu─ču benzeri kafatas─▒ma sokmamda yard─▒mc─▒ oldu, bu y├╝zden do─čru y├Âne gitmenizi sa─člamak i├žin 10 dakikal─▒k bir okuma oldu─čunu d├╝┼č├╝n├╝yorum.


11







B├╝y├╝k O bilmek i├žin t├╝m orada bilmek ister misin? Ben de.

Yani b├╝y├╝k OÔÇÖdan bahsetmek i├žin, i├žlerinde sadece bir ritmi olan kelimeleri kullanaca─č─▒m. Kelime ba┼č─▒na bir ses. K├╝├ž├╝k kelimeler h─▒zl─▒. Bu kelimeleri biliyorsunuz ve ben de ├Âyle. Kelimeleri tek bir sesle kullanaca─č─▒z. K├╝├ž├╝kler. Kullanaca─č─▒m─▒z t├╝m kelimeleri bilece─činize eminim!

┼×imdi, sen ve ben i┼čten konu┼čal─▒m. ├ço─ču zaman i┼čten ho┼članm─▒yorum. ├çal─▒┼čmay─▒ sever misin? Bunu yapabilirsin, ama yapmad─▒─č─▒mdan eminim.

Ben i┼če gitmeyi sevmiyorum. ─░┼čyerinde zaman ge├žirmeyi sevmiyorum. Yolum olsayd─▒, sadece oynamak ve e─členceli ┼čeyler yapmak isterdim. Sen de benim gibi hissediyor musun?

┼×imdi zaman zaman i┼če gitmem gerekiyor. Ac─▒ ama ger├žek. Bu y├╝zden, i┼čteyken bir kural─▒m var: Daha az i┼č yapmaya ├žal─▒┼č─▒yorum. Yapabildi─čim kadar i┼č yok. ├ľyleyse oynamaya gidiyorum!

Yani burada b├╝y├╝k haber: b├╝y├╝k O i┼č yapmamam i├žin bana yard─▒m edebilir! B├╝y├╝k O'yu tan─▒yorsam daha ├žok oynayabilirim. Daha az i┼č, daha ├žok oyun! B├╝y├╝k O'nun yapmama yard─▒m etti─či ┼čey budur.

┼×imdi baz─▒ i┼člerim var. Bu listeye sahibim: bir, iki, ├╝├ž, d├Ârt, be┼č, alt─▒. Bu listedeki her ┼čeyi eklemeliyim.

Vay, i┼čten nefret ediyorum. Ama oh iyi, bunu yapmak zorunday─▒m. ─░┼čte gidiyorum.

Bir art─▒ iki ├╝├ž ... art─▒ ├╝├ž alt─▒ ... ve d├Ârt ... bilmiyorum. Kayboldum. Kafamda yapmak benim i├žin ├žok zor. Bu t├╝r bir i┼č umrumda de─čil.

├ľyleyse i┼či yapmayal─▒m. Sen ve ben sadece bunun ne kadar zor oldu─čunu d├╝┼č├╝nelim. Alt─▒ say─▒ eklemek i├žin ne kadar i┼č yapmam gerekir?

─░yi, g├Ârelim bakal─▒m. Bir ya da iki eklemeliyim, sonra bunu ├╝├že ekleyip sonra onu d├Ârde eklemeliyimÔÇŽ Sonu├ž olarak, alt─▒ adede say─▒yorum. Bunu ├ž├Âzmek i├žin alt─▒ tane eklemeliyim.

─░┼čte bize bu matemati─čin ne kadar zor oldu─čunu s├Âylemek i├žin b├╝y├╝k O geliyor.

B├╝y├╝k O diyor ki: Bunu ├ž├Âzmek i├žin alt─▒ ek yapmal─▒y─▒z. Bir ila alt─▒, her ┼čey i├žin bir tane ekleyin. Alt─▒ k├╝├ž├╝k i┼č par├žas─▒ ... her i┼č par├žas─▒ birer eklemedir.

┼×imdi onlar─▒ eklemek i├žin i┼či yapmayaca─č─▒m. Ama ne kadar zor olaca─č─▒n─▒ biliyorum. Alt─▒ ek olacakt─▒.

Oh hay─▒r, ┼čimdi daha fazla i┼čim var. Sheesh. Bu t├╝r ┼čeyleri kim yapar?

┼×imdi benden bir ila on eklememi istediler! Neden bunu yapay─▒m? Bir ila alt─▒ eklemek istemedim. Bir ile on aras─▒ndaÔÇŽ iyiÔÇŽ bu daha da zor olurdu!

Daha ne kadar zor olurdu? Daha ne kadar i┼č yapmam gerekir? Daha fazla veya daha az ad─▒ma ihtiyac─▒m var m─▒?

San─▒r─▒m on ek yapmak zorunda kalaca─č─▒mÔÇŽ her biri i├žin bir ile on aras─▒nda bir tane. On, alt─▒dan fazla. Bir ila ondan, bir ila alt─▒dan daha fazla eklemek i├žin ├žok ├žal─▒┼čmak zorunda kalaca─č─▒m!

┼×u anda eklemek istemiyorum. Sadece bu kadar fazla eklemenin ne kadar zor oldu─čunu d├╝┼č├╝nmek istiyorum. Ve umar─▒m en k─▒sa s├╝rede oynamak i├žin.

Bir ila alt─▒ eklemek i├žin, bu biraz i┼čtir. Ama g├Âr├╝yorsunuz, bir ila ondan eklemek i├žin, bu daha ├žok i┼č mi?

B├╝y├╝k O senin arkada┼č─▒n ve benim. B├╝y├╝k O, ne kadar i┼č yapmam─▒z gerekti─čini d├╝┼č├╝nmemize yard─▒mc─▒ oluyor, b├Âylece plan yapabiliriz. Ve e─čer b├╝y├╝k O ile arkada┼čsak, o kadar da zor olmayan i┼čleri se├žmemize yard─▒m edebilir!

┼×imdi yeni i┼č yapmal─▒y─▒z. Oh hay─▒r. Bu i┼č ┼čeyini hi├ž sevmiyorum.

Yeni i┼č ┼čudur: Birinden n'ye her ┼čeyi ekleyin.

Bekleyin! N nedir? Onu ├Âzledim mi? Bana n'in ne oldu─čunu s├Âylemezsen nas─▒l birinden n'ye ekleyebilirim?

Ne oldu─čunu bilmiyorum. Bana s├Âylenmedi. Sen? Yok hay─▒r? Oh iyi. Yani i┼či yapamay─▒z. Whew.

Ancak ┼čimdi i┼či yapmayacak olsak da, e─čer bilseydik ne kadar zor olaca─č─▒n─▒ tahmin edebiliriz. Bir ┼čeyler eklemek zorunda kalaca─č─▒z, de─čil mi? Tabii ki!

┼×imdi burada b├╝y├╝k O geliyor ve bize bu i┼čin ne kadar zor oldu─čunu s├Âyleyecek. Diyor ki: birinden N'ye her ┼čeyi eklemek, birer birer O (n). Bunlar─▒ eklemek i├žin [n kere eklemeliyim biliyorum.] [1] Bu b├╝y├╝k O! Bize bir t├╝r i┼č yapman─▒n ne kadar zor oldu─čunu s├Âyl├╝yor.

Bana g├Âre, b├╝y├╝k, yava┼č, patron bir adam gibi b├╝y├╝k OÔÇÖyu d├╝┼č├╝n├╝yorum. ├çal─▒┼čmay─▒ d├╝┼č├╝n├╝yor, ama yapm─▒yor. "Bu i┼č h─▒zl─▒." Diyebilir. Ya da ÔÇťBu i┼č ├žok yava┼č ve zor!ÔÇŁ Diyebilir. Ama i┼či yapm─▒yor. Sadece i┼če bak─▒yor ve sonra ne kadar zaman alaca─č─▒n─▒ anlat─▒yor.

B├╝y├╝k O.'ya ├žok de─čer veriyorum. Neden? ├çal─▒┼čmay─▒ sevmiyorum! Kimse ├žal─▒┼čmay─▒ sevmiyor. Bu y├╝zden hepimiz b├╝y├╝k O'yu seviyoruz! Bize ne kadar h─▒zl─▒ ├žal─▒┼čabilece─čimizi s├Âyledi. ─░┼čin ne kadar zor oldu─čunu d├╝┼č├╝nmemize yard─▒m ediyor.

Ahh, daha fazla i┼č. ┼×imdi, i┼či yapmayal─▒m. Ancak, ad─▒m ad─▒m, bunu yapmak i├žin bir plan yapal─▒m.

Bize on kartl─▒k bir g├╝verte verdiler. Hepsi birbirine kar─▒┼čm─▒┼č durumda: yedi, d├Ârt, iki, alt─▒ÔÇŽ hi├ž do─čru de─čil. Ve ┼čimdi ... bizim i┼čimiz onlar─▒ s─▒ralamak.

Ergh. Bu ├žok i┼č gibi geliyor!

Bu g├╝verteyi nas─▒l s─▒ralayabiliriz? Bir plan─▒m var.

─░lk desteden, her bir kart ├žiftine, her bir ├žift i├žin ├žift desteyle bakaca─č─▒m. Bir ├žiftin ilk kart─▒ b├╝y├╝kse ve bu ├žiftin bir sonraki kart─▒ k├╝├ž├╝kse, onlar─▒ de─či┼čtiririm. Aksi takdirde, bir sonraki ├žifte giderim, ve b├Âyle devam eder ... ve yak─▒nda, g├╝verte yap─▒l─▒r.

G├╝verte bitti─činde, ┼čunu sordum: o pasta kartlar─▒ de─či┼čtirdim mi? E─čer ├Âyleyse, hepsini ├╝stten bir kez daha yapmal─▒y─▒m.

Bir noktada, bir anda, hi├žbir takas olmayacak ve bizim t├╝r g├╝verte yap─▒lacakt─▒. ├çok fazla i┼č!

Kartlar─▒ bu kurallara g├Âre s─▒ralamak ne kadar i┼č olurdu?

On kart─▒m var. Ve, ├žo─ču zaman - yani, e─čer ├žok fazla ┼čans─▒m yoksa - t├╝m desteyi on defaya kadar kullanmal─▒y─▒m, her seferinde destede on kartla takas etmeliyim.

Big O, yard─▒m et bana!

B├╝y├╝k O gelir ve der ki: n kart destesi i├žin, bu ┼čekilde s─▒ralamak i├žin O (N kare) zamanla yap─▒lacakt─▒r.

Neden n kare dedi?

Biliyorsunuz n kare n kere n. ┼×imdi anl─▒yorum: n kart destede n kez ne olabilece─čine kadar kontrol edildi. Bu, her biri n ad─▒ml─▒ iki d├Âng├╝d├╝r. Bu yap─▒lmas─▒ gereken ├žok i┼č var. ├çok i┼č, kesin!

┼×imdi b├╝y├╝k O, O (n kare) i┼či alaca─č─▒n─▒ s├Âyledi─činde, burun ├╝zerinde n kare eklenmesi anlam─▒na gelmez. Baz─▒ durumlar i├žin biraz daha az olabilir. Ancak en k├Ât├╝ durumda, g├╝verteyi s─▒ralamak i├žin ├žal─▒┼čmalar─▒n n kare ad─▒mlara yak─▒n olmas─▒ bekleniyor.

┼×imdi burada b├╝y├╝k O bizim dostumuz.

B├╝y├╝k O ┼čunu vurguluyor: n b├╝y├╝d├╝k├že, kartlar─▒ s─▒ralad─▒─č─▒m─▒zda, i┼č, eski ┼čeyler eklemek yerine, ├çOK DAHA FAZLASI oluyor. Bunu nas─▒l biliyoruz?

E─čer n ├žok b├╝y├╝rse, n ya da n kareye ne ekleyece─čimiz umurumda de─čil.

B├╝y├╝k n i├žin, n kare n'den b├╝y├╝kt├╝r.

Big O bize bir ┼čeyi s─▒ralaman─▒n bir ┼čeyleri eklemekten daha zor oldu─čunu s├Âyler. O (n kare), b├╝y├╝k n i├žin O (n) 'den fazlad─▒r. Bunun anlam─▒ ┼čudur: n ger├žekten b├╝y├╝rse, kar─▒┼č─▒k ┼čeyleri kar─▒┼čt─▒rmak, n kar─▒┼č─▒k ┼čey eklemek yerine daha fazla zaman almal─▒d─▒r.

B├╝y├╝k O i┼či bizim i├žin ├ž├Âzmez. B├╝y├╝k O bize i┼čin ne kadar zor oldu─čunu s├Âyl├╝yor.

Bir deste kart─▒m var. Onlar─▒ s─▒ralad─▒m. Yard─▒m ettin. Te┼čekk├╝rler.

Kartlar─▒ s─▒ralaman─▒n daha h─▒zl─▒ bir yolu var m─▒? B├╝y├╝k O bize yard─▒m edebilir mi?

Evet, daha h─▒zl─▒ bir yol var! ├ľ─črenmesi biraz zaman al─▒yor, ama i┼če yar─▒yor ... ve olduk├ža h─▒zl─▒ ├žal─▒┼č─▒yor. Siz de deneyebilirsiniz, ancak her ad─▒mda zaman ay─▒r─▒n ve yerinizi kaybetmeyin.

Bir desteyi s─▒ralaman─▒n bu yeni yolunda, bir s├╝re ├Ânce yapt─▒─č─▒m─▒z gibi kart ├žiftlerini kontrol etmiyoruz. ─░┼čte bu desteyi s─▒ralamak i├žin yeni kurallar─▒n─▒z:

Bir: ┼×u anda ├╝zerinde ├žal─▒┼čt─▒─č─▒m─▒z destenin bir kart─▒n─▒ se├žiyorum. ─░stersen benim i├žin bir tane se├žebilirsin. (Bunu ilk yapt─▒─č─▒m─▒zda, ÔÇť┼ču an ├╝zerinde ├žal─▒┼čt─▒─č─▒m─▒z destenin bir par├žas─▒ÔÇŁ elbette t├╝m g├╝vertedir.)

─░ki: Se├žti─činiz kart─▒n ├╝st├╝ne desteyi yayd─▒m. Bu yay─▒lma nedir? nas─▒l yay─▒l─▒r─▒m? Ba┼člang─▒├ž ÔÇőÔÇőkart─▒ndan tek tek a┼ča─č─▒ iniyorum ve a├ž─▒l─▒┼č kart─▒ndan daha y├╝ksek olan bir kart ar─▒yorum.

├ť├ž: Son karttan yukar─▒ do─čru giderim ve a├ž─▒l─▒┼č kart─▒ndan daha d├╝┼č├╝k bir kart arar─▒m.

Bu iki kart─▒ bulduktan sonra, onlar─▒ de─či┼čtiriyorum ve de─či┼čtirilebilecek daha fazla kart aramaya devam ediyorum. Yani, ─░kinci ad─▒ma geri d├Ân├╝yorum ve kart─▒ se├žerek daha fazlas─▒n─▒ se├žtiniz.

Bir noktada, bu d├Âng├╝ (─░kiden ├ť├že) bitecektir. Bu araman─▒n her iki yar─▒s─▒ da splay kart─▒nda bulu┼čtu─čunda biter. Daha sonra, ad─▒m 1'de se├žti─činiz kartla desteyi az ├Ânce a├žt─▒k. ┼×imdi, ba┼člang─▒├ž ÔÇőÔÇőyak─▒n─▒ndaki t├╝m kartlar, a├ž─▒l─▒┼č kart─▒ndan daha d├╝┼č├╝k; ve sonuna yak─▒n olan kartlar, a├ž─▒l─▒┼č kart─▒ndan daha y├╝ksektir. Harika numara!

D├Ârt (ve bu e─členceli k─▒s─▒m): ┼×imdi iki k├╝├ž├╝k deste var, bir tanesi splay karttan daha d├╝┼č├╝k ve bir tane daha y├╝ksek. ┼×imdi her k├╝├ž├╝k g├╝vertede birinci ad─▒ma ge├žiyorum! Yani, ilk k├╝├ž├╝k g├╝vertede Bir ad─▒mdan ba┼čl─▒yorum ve bu i┼č bitti─činde, bir sonraki k├╝├ž├╝k g├╝vertede Bir ad─▒mdan ba┼čl─▒yorum.

Desteyi par├žalara ay─▒r─▒p her par├žay─▒ daha k├╝├ž├╝k ve daha k├╝├ž├╝k olarak s─▒ral─▒yorum ve bir zamanlar yapacak daha fazla i┼čim yok. ┼×imdi bu t├╝m kurallara g├Âre yava┼č g├Âr├╝nebilir. Ama g├╝ven bana, hi├ž yava┼č de─čil. Her ┼čeyi s─▒ralamak i├žin ilk y├Ântemden ├žok daha az i┼č!

Bu t├╝rden ne denir? Buna H─▒zl─▒ S─▒ralama! Bu s─▒ralama CAR Hoare adl─▒ bir adam taraf─▒ndan yap─▒ld─▒ ve H─▒zl─▒ S─▒ralama olarak adland─▒rd─▒. ┼×imdi, H─▒zl─▒ S─▒ralama her zaman kullan─▒l─▒r!

H─▒zl─▒ S─▒ralama k├╝├ž├╝k olanlar─▒ b├╝y├╝k destelerden ay─▒r─▒r. Yani k├╝├ž├╝k i┼člerde b├╝y├╝k i┼čleri par├žalara ay─▒r─▒yor.

Hmmm. San─▒r─▒m orada bir kural olabilir. B├╝y├╝k g├Ârevleri k├╝├ž├╝k yapmak i├žin bunlar─▒ ay─▒r─▒n.

Bu s─▒ralama olduk├ža h─▒zl─▒. Ne kadar h─▒zl─▒? B├╝y├╝k O bize ┼čunlar─▒ s├Âyler: bu durumda, bu durumda O (n log n) yap─▒lmas─▒ gereken i┼čler gerekir.

─░lk s─▒ralamadan daha az m─▒ h─▒zl─▒ m─▒? B├╝y├╝k O, l├╝tfen yard─▒m et!

─░lk s─▒ralama O (n kare) idi. Ancak H─▒zl─▒ S─▒ralama O (n log n) 'dir. N log n nin n kareden az oldu─čunu biliyorsunuz, b├╝y├╝k n i├žin, de─čil mi? Peki, bu h─▒zl─▒ s─▒ralama h─▒zl─▒ oldu─čunu biliyoruz!

Bir g├╝verte s─▒ralamak zorunda kal─▒rsan─▒z, en iyi yol nedir? Ne istersen yapabilirsin, ama ben H─▒zl─▒ S─▒rala'y─▒ se├žerdim.

Neden H─▒zl─▒ S─▒ralamay─▒ se├žiyorum? Tabii ki ├žal─▒┼čmaktan ho┼članm─▒yorum! Yapabildi─čim kadar ├žabuk i┼č yap─▒lmas─▒n─▒ istiyorum.

H─▒zl─▒ S─▒ralama'n─▒n daha az i┼če yarad─▒─č─▒n─▒ nas─▒l bilebilirim? O (n log n) 'in O (n kare)' den k├╝├ž├╝k oldu─čunu biliyorum. O daha k├╝├ž├╝k, bu y├╝zden H─▒zl─▒ S─▒ralama daha az i┼č!

Art─▒k arkada┼č─▒m Big O.'y─▒ tan─▒yorsun. Daha az i┼č yapmam─▒za yard─▒m ediyor. Ve e─čer b├╝y├╝k O biliyorsan─▒z, daha az i┼č yapabilirsiniz!

Hepsini benimle ├Â─črendin! Sen ├žok ak─▒ll─▒s─▒n! ├çok te┼čekk├╝r ederim!

┼×imdi bu i┼č bitti, haydi oynayal─▒m!


[1]: Hile yapman─▒n ve her ┼čeyi bir kereden nÔÇÖye eklemenin bir yolu var. Gauss ad─▒nda bir ├žocuk bunu sekiz ya┼č─▒ndayken buldu. Ben o kadar ak─▒ll─▒ de─čilim, bu y├╝zden bana nas─▒l yapt─▒─č─▒n─▒ sorma .


11







Zaman karma┼č─▒kl─▒─č─▒n─▒ hesaplamak i├žin en yayg─▒n metrik olan Zaman Karma┼č─▒kl─▒─č─▒n─▒ anlamak i├žin daha basit bir y├Ântemim B├╝y├╝k O notasyonu. Bu, t├╝m sabit fakt├Ârleri ortadan kald─▒r─▒r, b├Âylece N, sonsuzlu─ča yakla┼č─▒rken, ├žal─▒┼čma s├╝resi N ile ili┼čkili olarak tahmin edilebilir. Genel olarak ┼č├Âyle d├╝┼č├╝nebilirsiniz:

 statement;
 

Sabittir. ─░fadenin ├žal─▒┼čma s├╝resi N ile ili┼čkili olarak de─či┼čmeyecek

 for ( i = 0; i < N; i++ )
  statement;
 

Do─črusald─▒r. D├Âng├╝n├╝n ├žal─▒┼čma s├╝resi do─črudan N ile orant─▒l─▒d─▒r. N iki kat─▒na ├ž─▒kt─▒─č─▒nda ├žal─▒┼čma s├╝resi de artar.

 for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}
 

─░kinci dereceden. ─░ki d├Âng├╝n├╝n ├žal─▒┼čma s├╝resi N karesiyle orant─▒l─▒d─▒r. N iki kat─▒na ├ž─▒kt─▒─č─▒nda ├žal─▒┼čma s├╝resi N * N kadar artar.

 while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}
 

Logaritmiktir. Algoritman─▒n ├žal─▒┼čma s├╝resi, N'nin 2'ye b├Âl├╝nebilece─či say─▒ ile orant─▒l─▒d─▒r. Bunun nedeni, algoritman─▒n ├žal─▒┼čma alan─▒n─▒ her yinelemenin yar─▒s─▒na b├Âlmesidir.

 void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}
 

N * log'dur (N). ├çal─▒┼čma s├╝resi logaritmik olan N d├Âng├╝lerinden (yinelemeli veya ├Âzyinelemeli) olu┼čur, bu nedenle algoritma do─črusal ve logaritmik bir kombinasyondur.

Genel olarak, her ├Â─čeyle bir boyutta bir ┼čey yapmak do─črusald─▒r, her ├Â─čeyle iki boyutta bir ┼čey yapmak ikinci derecedendir ve ├žal─▒┼čma alan─▒n─▒ ikiye b├Âlmek logaritmiktir. K├╝bik, ├╝stel ve karek├Âk gibi ba┼čka Big O ├Ânlemleri de var, ancak neredeyse o kadar yayg─▒n de─čiller. B├╝y├╝k O notasyonu, ├Âl├ž├╝ birimi oldu─ču O () olarak tan─▒mlan─▒r. H─▒zl─▒ ba─člant─▒ algoritmas─▒, O (N * log (N)) olarak tan─▒mlan─▒r.

Not: Bunlar─▒n hi├žbiri en iyi, ortalama ve en k├Ât├╝ durum ├Ânlemlerini dikkate almam─▒┼čt─▒r. Her birinin kendi Big O notasyonu vard─▒r. Ayr─▒ca bunun ├žok basit bir a├ž─▒klama oldu─čunu unutmay─▒n. B├╝y├╝k O en yayg─▒n olan─▒d─▒r, ancak g├Âsterdi─čimden daha karma┼č─▒k. B├╝y├╝k omega, k├╝├ž├╝k o ve b├╝y├╝k teta gibi ba┼čka g├Âsterimler de vard─▒r. Muhtemelen bir algoritma analiz kursu d─▒┼č─▒nda onlarla kar┼č─▒la┼čmazs─▒n─▒z.

  • Daha fazlas─▒n─▒ g├Âr├╝n: Here

9







Diyelim ki Harry Potter: Amazon'dan 8-Film Koleksiyonunu [Blu-ray] tamamlay─▒n ve ayn─▒ film koleksiyonunu ayn─▒ anda ├ževrimi├ži indirin. Hangi y├Ântemin daha h─▒zl─▒ oldu─čunu test etmek istiyorsunuz. Teslimat─▒n gelmesi neredeyse bir g├╝n s├╝r├╝yor ve indirme i┼člemi yakla┼č─▒k 30 dakika ├Ânce tamamland─▒. Harika! Bu y├╝zden s─▒k─▒ bir yar─▒┼č.

Y├╝z├╝klerin Efendisi, Alacakaranl─▒k, Kara ┼×├Âvalye ├ť├žlemesi, vs. gibi birka├ž Blu-ray filmi sipari┼č edip, ├ževrimi├ži olarak t├╝m filmleri ayn─▒ anda indiriyorsam ne olur? Bu kez, teslimat─▒n tamamlanmas─▒ bir g├╝n s├╝r├╝yor, ancak ├ževrimi├ži indirmenin tamamlanmas─▒ 3 g├╝n s├╝r├╝yor. Online al─▒┼čveri┼č i├žin, sat─▒n al─▒nan ├╝r├╝n├╝n (girdi) say─▒s─▒ teslimat s├╝resini etkilemez. ├ç─▒k─▒┼č sabittir. Buna O (1) diyoruz .

├çevrimi├ži indirme i├žin, indirme s├╝resi do─črudan film dosyas─▒ boyutlar─▒yla (giri┼č) orant─▒l─▒d─▒r. Buna O (n) diyoruz .

Deneylerden, ├ževrimi├ži al─▒┼čveri┼čin, ├ževrimi├ži indirmeden daha iyi ├Âl├žeklendi─čini biliyoruz. B├╝y├╝k O g├Âsterimini anlamak ├žok ├Ânemlidir ├ž├╝nk├╝ algoritmalar─▒n ├Âl├žeklenebilirli─čini ve verimlili─čini analiz etmenize yard─▒mc─▒ olur .

Not: B├╝y├╝k O notasyonu bir algoritman─▒n en k├Ât├╝ senaryosunu temsil eder . Diyelim ki, O (1) ve O (n) yukar─▒daki ├Ârne─čin en k├Ât├╝ senaryolar─▒d─▒r.

Referans : http://carlcheo.com/compsci


9


2015-12-06





Varsayal─▒m ki , n b├╝y├╝kl├╝─č├╝nde veri k├╝mesine sahip bir ┼čey yapmas─▒ gereken A algoritmas─▒ndan bahsediyoruz .

├ľyleyse O( <some expression X involving n> ) , basit ─░ngilizce dilinde:

A'y─▒ ├žal─▒┼čt─▒r─▒rken ┼čanss─▒zsan─▒z, tamamlanmas─▒ X (n) i┼člemlerini alabilir.

O s─▒rada da, baz─▒ i┼člevler (olarak onlar─▒ d├╝┼č├╝n├╝yorum vard─▒r uygulamalar aras─▒nda X (n) olduk├ža s─▒k meydana gelme e─čilimindedir). Bu iyi bilinen ve kolayca kar┼č─▒la┼čt─▒r─▒labilir olan (├Ârnek olarak: 1 , Log N , N , N^2 , N! , vs ..)

Bahsederken bu kar┼č─▒la┼čt─▒rarak A ve di─čer algoritmalar, bunlar─▒n operasyonlar say─▒s─▒na g├Âre algoritmalar─▒ s─▒ralamak kolayd─▒r olabilir (en k├Ât├╝ durum) tamamlamak i├žin gereklidir.

Genel olarak hedefimiz, bir algoritmay─▒ A bulmak veya yap─▒land─▒rmak X(n) , m├╝mk├╝n oldu─ču kadar d├╝┼č├╝k bir say─▒ d├Ând├╝ren bir i┼čleve sahip olacak ┼čekilde olacakt─▒r .


9







Kafan─▒zda uygun bir sonsuzluk kavram─▒ varsa, o zaman ├žok k─▒sa bir a├ž─▒klama vard─▒r:

Big O notasyonu size sonsuz b├╝y├╝k bir problemi ├ž├Âzmenin maliyetini s├Âyler.

Ve ayr─▒ca

Sabit fakt├Ârler ihmal edilebilir

Algoritman─▒z─▒ iki kat daha h─▒zl─▒ ├žal─▒┼čt─▒rabilecek bir bilgisayara y├╝kseltirseniz, b├╝y├╝k O notalamas─▒ bunu fark etmez. Sabit fakt├Âr iyile┼čtirmeleri, b├╝y├╝k O g├Âsteriminin ├žal─▒┼čt─▒─č─▒ ├Âl├žekte bile fark edilemeyecek kadar k├╝├ž├╝kt├╝r. Bunun, b├╝y├╝k O notasyonu tasar─▒m─▒n─▒n kas─▒tl─▒ bir par├žas─▒ oldu─čuna dikkat edin.

Bununla birlikte, sabit bir fakt├Ârden "daha b├╝y├╝k" herhangi bir ┼čey tespit edilebilse de.

B├╝y├╝kl├╝─č├╝ yakla┼č─▒k sonsuz olarak kabul edilebilecek kadar "b├╝y├╝k" olan hesaplamalar yapmakla ilgilendi─činde, b├╝y├╝k O notu yakla┼č─▒k olarak probleminizi ├ž├Âzmenin maliyetidir.


Yukar─▒dakilerin bir anlam─▒ yoksa, kafan─▒zda uyumlu sezgisel bir sonsuzluk kavram─▒ yoktur ve muhtemelen yukar─▒dakilerin t├╝m├╝n├╝ g├Âz ard─▒ etmelisiniz; bu fikirleri titizle┼čtirmenin ya da sezgisel olarak yararl─▒ olmad─▒klar─▒n─▒ a├ž─▒klamam─▒n tek yolu, ilk ├Ânce size b├╝y├╝k O notalar─▒n─▒ ya da benzerlerini ├Â─čretmektir. (Gelecekte b├╝y├╝k O g├Âsterimini iyi anlad─▒─č─▒n─▒zda, bu fikirlerin tekrar g├Âzden ge├žirilmesi faydal─▒ olabilir)


8


2015-05-16





ÔÇťB├╝y├╝k OÔÇŁ yaz─▒m─▒na dair basit bir ─░ngilizce a├ž─▒klama nedir?

Çok Hızlı Not:

"B├╝y├╝k O" daki O, "D├╝zen" (veya kesin olarak "") "anlam─▒na gelir,
bu nedenle kelimenin tam anlam─▒yla, bunlar─▒ kar┼č─▒la┼čt─▒rmak i├žin bir ┼čeyler sipari┼č etmek i├žin kullan─▒ld─▒─č─▒ fikrini alabilirsiniz.

  • "B├╝y├╝k O" iki ┼čey yapar:

    1. Bilgisayar─▒n─▒zda bir g├Ârevi ger├žekle┼čtirmek i├žin ka├ž tane y├Ântem uyguland─▒─č─▒n─▒ tahmin eder.
    2. ─░yi olup olmad─▒─č─▒n─▒ belirlemek i├žin di─čerleriyle kar┼č─▒la┼čt─▒rma s├╝recini kolayla┼čt─▒rmak?
    3. ÔÇťB├╝y├╝k OÔÇŁ, yukar─▒daki ikisini standart hale getirerek ba┼čar─▒r Notations .
  • En ├žok kullan─▒lan yedi g├Âsterim vard─▒r

    1. O (1), bilgisayar─▒n─▒z─▒n 1 ad─▒mla yap─▒lan bir i┼č yapt─▒─č─▒ anlam─▒na gelir, m├╝kemmel, Sipari┼č No.1
    2. O (logN), bilgisayar─▒n─▒z─▒n logN ad─▒mlarla bir g├Ârevi tamamlad─▒─č─▒ anlam─▒na gelir , iyi, Sipari┼č No.2
    3. O (N), N ad─▒mlarla bir i┼či bitir , adil, Sipari┼č No. 3
    4. O (NlogN), O(NlogN) ad─▒mlarla bir g├Ârevi bitiriyor , iyi de─čil, Sipari┼č No.4
    5. O (N ^ 2), N^2 ad─▒mlarla bir i┼č yap─▒n , bu k├Ât├╝, Sipari┼č No. 5
    6. O (2 ^ N), 2^N ad─▒mlarla bir g├Ârevi halledin , korkun├ž, Sipari┼č No. 6
    7. O (N!), Ad─▒mlarla bir i┼č bul N! , ├žok korkun├ž, Sipari┼č No.7


g├Âr├╝nt├╝ tan─▒m─▒n─▒ buraya girin

O(N^2) Not ald─▒─č─▒n─▒z─▒ varsayal─▒m , yaln─▒zca y├Ântemin bir g├Ârevi ba┼čarmak i├žin N * N ad─▒mlar att─▒─č─▒n─▒ de─čil ayn─▒ zamanda O(NlogN) s─▒ralamas─▒ndan da iyi olmad─▒─č─▒n─▒ g├Âr├╝yorsunuz .

L├╝tfen sat─▒r sonundaki s─▒ray─▒ not edin, yaln─▒zca daha iyi anlaman─▒z i├žin. T├╝m olas─▒l─▒klar g├Âz ├Ân├╝nde bulundurulursa 7'den fazla g├Âsterim vard─▒r.

CS'de, bir g├Ârevi yerine getirmek i├žin at─▒lan ad─▒mlara algoritmalar denir.
Terminolojide, bir algoritman─▒n performans─▒n─▒ veya karma┼č─▒kl─▒─č─▒n─▒ tan─▒mlamak i├žin Big O notasyonu kullan─▒l─▒r.

Ek olarak, B├╝y├╝k O en k├Ât├╝ durumu belirler veya ├ťst S─▒n─▒rl─▒ ad─▒mlar─▒ ├Âl├žer.
En iyi durum i├žin Big-╬ę (Big-Omega) bak─▒n.

B├╝y├╝k ╬ę (B├╝y├╝k Omega) notasyonu (makale) | Han Akademisi

  • ├ľzet
    "B├╝y├╝k O" algoritman─▒n performans─▒n─▒ a├ž─▒klar ve de─čerlendirir.

    veya resmen hitap edersek, "B├╝y├╝k O" algoritmalar─▒ s─▒n─▒fland─▒r─▒r ve kar┼č─▒la┼čt─▒rma s├╝recini standartla┼čt─▒r─▒r.


7







Bakman─▒n en basit yolu (d├╝z ─░ngilizce)

Giri┼č parametresi say─▒s─▒n─▒n bir algoritman─▒n ├žal─▒┼čma s├╝resini nas─▒l etkiledi─čini g├Ârmeye ├žal─▒┼č─▒yoruz. Uygulaman─▒z─▒n ├žal─▒┼čma s├╝resi, giri┼č parametresi say─▒s─▒yla orant─▒l─▒ysa, n nin B├╝y├╝k O oldu─ču s├Âylenir.

Yukar─▒daki ifade iyi bir ba┼člang─▒├žt─▒r ancak tamamen do─čru de─čildir.

Daha do─čru bir a├ž─▒klama (matematiksel)

varsaymak

n = giri┼č parametresi say─▒s─▒

T (n) = Algoritman─▒n ├žal─▒┼čma s├╝resini n'nin bir i┼člevi olarak ifade eden as─▒l i┼člev

c = sabit

f (n) = Algoritman─▒n ├žal─▒┼čma s├╝resini n'nin bir i┼člevi olarak ifade eden yakla┼č─▒k bir i┼člev

O zaman B├╝y├╝k O ile ilgili olarak, f (n) yakla┼č─▒m─▒n─▒n a┼ča─č─▒daki ko┼čul ge├žerli oldu─ču s├╝rece yeterince iyi oldu─ču kabul edilir.

 lim     T(n) ÔëĄ c├Śf(n)
nÔćĺÔł×
 

E┼čitlik n'nin sonsuzlu─ča yakla┼č─▒rken, n'nin T'si, n'nin c zaman─▒na e┼čit veya daha k├╝├ž├╝k oldu─ču gibi denklem okunur.

B├╝y├╝k O notasyonunda, bu

 T(n)ÔłłO(n)
 

Bu, n nin T de─čeri n nin b├╝y├╝k O oldu─ču ┼čeklinde okunur.

─░ngilizceye d├Ân

Yukar─▒daki matematiksel tan─▒mlamaya dayanarak, algoritman─▒z─▒n n'nin b├╝y├╝k O oldu─čunu s├Âylerseniz, bunun n'nin (giri┼č parametresi say─▒s─▒) veya daha h─▒zl─▒ oldu─ču anlam─▒na gelir . Algoritman─▒z n b├╝y├╝k O ise, o zaman n kare otomatik olarak B├╝y├╝k O olur.

N nin b├╝y├╝k O, algoritmam─▒n en az─▒ndan bu kadar h─▒zl─▒ ├žal─▒┼čt─▒─č─▒n─▒ g├Âsterir. Algoritman─▒z─▒n Big O notasyonuna bak─▒p onun yava┼č oldu─čunu s├Âyleyemezsiniz. Sadece h─▒zl─▒ diyebilirsin.

UC Berkley'den Big O hakk─▒nda bir video e─čitimi i├žin bunu kontrol edin . Bu asl─▒nda basit bir kavram. Bunu a├ž─▒klayan profes├Âr Shewchuck'─▒ (tanr─▒ d├╝zeyinde ├Â─čretmen) duyarsan─▒z, "Ah, hepsi bu kadar!" Diyeceksiniz.


6







├ľzellikle b├╝y├╝k matematik g├Âsterimi olmayan biri i├žin b├╝y├╝k O notasyonu hakk─▒nda ger├žekten harika bir a├ž─▒klama buldum.

https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

Big O notasyonu, Computer Science'da algoritman─▒n performans─▒n─▒ veya karma┼č─▒kl─▒─č─▒n─▒ tan─▒mlamak i├žin kullan─▒l─▒r. B├╝y├╝k O, ├Âzellikle en k├Ât├╝ senaryoyu tan─▒mlar ve bir algoritma taraf─▒ndan gereken y├╝r├╝tme zaman─▒n─▒ veya kullan─▒lan alan─▒ (├Ârne─čin bellekte veya diskte) tan─▒mlamak i├žin kullan─▒labilir.

Programlama ─░ncileri'ni veya di─čer bir Bilgisayar Bilimi kitab─▒n─▒ okuyan ve Matematikte bir temeli olmayan bir ki┼či, O (N log N) ya da g├Âr├╝n├╝┼čte ├ž─▒lg─▒nca s├Âzdiziminden bahseden b├Âl├╝mlere ula┼čt─▒─č─▒nda bir duvara ├žarpacak. Umar─▒m bu makale, Big O ve Logaritma'n─▒n temellerini anlaman─▒za yard─▒mc─▒ olacakt─▒r.

├ľnce bir programc─▒ ve bir matematik├ži ikinci (ya da belki ├╝├ž├╝nc├╝ ya da d├Ârd├╝nc├╝) olarak, B├╝y├╝k O'yu iyice anlaman─▒n en iyi yolunu kodda baz─▒ ├Ârnekler ├╝retmek oldu─čunu buldum. Bu nedenle, a┼ča─č─▒da m├╝mk├╝n olan baz─▒ a├ž─▒klamalar ve ├Ârnekler ile birlikte baz─▒ yayg─▒n b├╝y├╝me s─▒ralar─▒ var.

O (1)

O (1), giri┼č veri k├╝mesinin boyutuna bak─▒lmaks─▒z─▒n her zaman ayn─▒ zamanda (veya bo┼člukta) ├žal─▒┼čacak bir algoritmay─▒ a├ž─▒klar.

 bool IsFirstElementNull(IList<string> elements) {
    return elements[0] == null;
}
 

O (N)

O (N), performans─▒ do─črusal olarak ve girdi veri setinin b├╝y├╝kl├╝─č├╝ ile do─čru orant─▒l─▒ olarak b├╝y├╝yen bir algoritmay─▒ tan─▒mlar. A┼ča─č─▒daki ├Ârnek ayn─▒ zamanda B├╝y├╝k O'nun en k├Ât├╝ durum performans senaryosunu nas─▒l destekledi─čini g├Âstermektedir; for d├Âng├╝s├╝n├╝n herhangi bir yinelemesi s─▒ras─▒nda e┼čle┼čen bir dize bulunabilir ve i┼člev erken d├Ânecektir, ancak Big O notasyonu her zaman algoritman─▒n maksimum yineleme say─▒s─▒n─▒ ger├žekle┼čtirece─či ├╝st limiti kabul edecektir.

 bool ContainsValue(IList<string> elements, string value) {
    foreach (var element in elements)
    {
        if (element == value) return true;
    }

    return false;
} 
 

0 (N 2 )

O (N 2 ), performans─▒, girdi veri setinin boyutunun karesiyle do─črudan orant─▒l─▒ olan bir algoritmay─▒ temsil eder. Bu, veri k├╝mesi ├╝zerinde i├ž i├že yineleme i├žeren algoritmalarda yayg─▒nd─▒r. Derin i├ž i├že tekrarlamalar O (N neden olur 3 ), O (N 4 vb)

 bool ContainsDuplicates(IList<string> elements) {
    for (var outer = 0; outer < elements.Count; outer++)
    {
        for (var inner = 0; inner < elements.Count; inner++)
        {
            // Don't compare with self
            if (outer == inner) continue;

            if (elements[outer] == elements[inner]) return true;
        }
    }

    return false;
}
 

0 (2 N )

O (2 N ), b├╝y├╝mesi girdi veri setine her bir ilave ile ikiye katlanan bir algoritmay─▒ belirtir. Bir O (2 N ) fonksiyonunun b├╝y├╝me e─črisi ├╝steldir - ├žok s─▒─č ba┼člar, sonra meteorik olarak y├╝kselir. Bir O (2 N ) fonksiyonunun bir ├Ârne─či , Fibonacci say─▒lar─▒n─▒n ├Âzyinelemeli hesaplamas─▒d─▒r:

 int Fibonacci(int number) {
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}
 

Logaritma

Logaritmalar a├ž─▒klamak i├žin biraz daha yanl─▒┼čt─▒r, bu y├╝zden ortak bir ├Ârnek kullanaca─č─▒m:

─░kili arama, s─▒ralanm─▒┼č veri k├╝melerini aramak i├žin kullan─▒lan bir tekniktir. Veri setinin orta ├Â─česini, esas olarak medyan─▒ se├žerek ├žal─▒┼č─▒r ve onu bir hedef de─čerle kar┼č─▒la┼čt─▒r─▒r. De─čerler e┼čle┼čirse ba┼čar─▒ d├Ând├╝r├╝l├╝r. Hedef de─čer, prob eleman─▒n─▒n de─čerinden y├╝ksekse, veri k├╝mesinin ├╝st yar─▒s─▒n─▒ al─▒r ve buna kar┼č─▒ ayn─▒ i┼člemi ger├žekle┼čtirir. Benzer ┼čekilde, hedef de─čer prob eleman─▒n─▒n de─čerinden d├╝┼č├╝kse, i┼člemi alt yar─▒ya kar┼č─▒ ger├žekle┼čtirir. De─čer bulunana kadar veya veri k├╝mesini art─▒k ay─▒ramaya ba┼člayana kadar her yinelemeyle ayarlanan verileri yar─▒ya indirmeye devam edecektir.

Bu algoritma tipi O (log N) olarak tan─▒mlanm─▒┼čt─▒r. ─░kili arama ├Ârne─činde a├ž─▒klanan veri k├╝melerinin yinelemeli yar─▒s─▒, ba┼člang─▒├žta zirveye ├ž─▒kan ve veri k├╝melerinin b├╝y├╝kl├╝─č├╝ artt─▒k├ža yava┼č yava┼č d├╝zle┼čen bir b├╝y├╝me e─črisi olu┼čturur, ├Ârne─čin 10 ├Â─če i├žeren bir girdi veri k├╝mesinin tamamlanmas─▒ bir saniye s├╝rer; 100 ├Â─če i├žeren iki saniye s├╝rer ve 1000 ├Â─če i├žeren bir veri ├╝├ž saniye s├╝recektir. Giri┼č veri setinin b├╝y├╝kl├╝─č├╝n├╝n iki kat─▒na ├ž─▒kar─▒lmas─▒, algoritman─▒n tek bir yinelemesinden sonra b├╝y├╝menin ├╝zerinde ├žok az etkiye sahiptir, b├Âylece veri seti yar─▒ya iner ve bu nedenle boyutun yar─▒s─▒ kadar bir giri┼č veri setiyle ayn─▒ olur. Bu, b├╝y├╝k veri k├╝meleriyle u─čra┼č─▒rken ikili arama gibi algoritmalar─▒ olduk├ža verimli k─▒lar.


5


2017-01-29





Bu ├žok basitle┼čtirilmi┼č bir a├ž─▒klamad─▒r, ancak umar─▒m en ├Ânemli detaylar─▒ kapsar.

Diyelim ki problemle ba┼ča ├ž─▒kma algoritman─▒z baz─▒ 'fakt├Ârlere' ba─čl─▒, ├Ârne─čin N ve X yapal─▒m.

N ve X'e ba─čl─▒ olarak, algoritman─▒z baz─▒ i┼člemlere ihtiya├ž duyar, ├Ârne─čin WORST durumunda oldu─ču gibi 3(N^2) + log(X) .

Big-O sabit fakt├Âr├╝ (aka 3) ├žok fazla ├Ânemsemedi─činden, algoritman─▒z─▒n Big-O'su O(N^2 + log(X)) . Temel olarak 'bununla birlikte en k├Ât├╝ durum ├Âl├žekleri i├žin algoritman─▒z─▒n ihtiya├ž duydu─ču i┼člem miktar─▒n─▒' ├ževirir.


4


2015-10-11





├Âns├Âz

algoritma : Bir problemin ├ž├Âz├╝m├╝ i├žin prosed├╝r / form├╝l


Algoritmalar─▒ nas─▒l analiz edebilir ve algoritmalar─▒ birbirleriyle nas─▒l kar┼č─▒la┼čt─▒rabiliriz?

├ľrnek: Sizden ve bir arkada┼č─▒n─▒zdan 0'dan N'ye kadar olan say─▒lar─▒ toplayan bir fonksiyon yaratman─▒z isteniyor. f (x) ile geliyorsunuz ve arkada┼č─▒n─▒z g (x) ile geliyor. Her iki fonksiyon da ayn─▒ sonuca, ancak farkl─▒ bir algoritmaya sahip. Algoritmalar─▒n verimlili─čini objektif olarak kar┼č─▒la┼čt─▒rmak i├žin Big-O notasyonu kullan─▒yoruz .

Big-O notasyonu: giri┼č keyfi olarak b├╝y├╝d├╝k├že ├žal─▒┼čma zaman─▒n─▒n giri┼če g├Âre ne kadar h─▒zl─▒ b├╝y├╝mesi gerekti─čini a├ž─▒klar .

3 anahtar teslim:

  1. Kar┼č─▒la┼čt─▒rma b├╝y├╝r ne kadar h─▒zl─▒ ├žal─▒┼čma zaman─▒ DE─×─░L kesin ├žal─▒┼čt─▒r─▒c─▒lar─▒ kar┼č─▒la┼čt─▒rmak (donan─▒m ba─čl─▒d─▒r)
  2. Sadece ├žal─▒┼čma zaman─▒ ile ilgilenen giri┼če g├Âre b├╝y├╝r (n)
  3. As n keyfi b├╝y├╝k olur (sonsuza d├╝┼č├╝n├╝n) AKA b├╝y├╝k al─▒r n olarak, ┼čartlarda odak bu h─▒zl─▒ b├╝y├╝yecek asimptotik analizi

Uzay karma┼č─▒kl─▒─č─▒: zaman karma┼č─▒kl─▒─č─▒n─▒n yan─▒ s─▒ra, uzay karma┼č─▒kl─▒─č─▒na da ├Ânem veriyoruz (bir algoritman─▒n ne kadar bellek / alan kulland─▒─č─▒). ─░┼člemlerin zaman─▒n─▒ kontrol etmek yerine, bellek tahsisinin boyutunu kontrol ediyoruz.


4