O (log n) tam olarak ne anlama geliyor?


Al─▒nan cevaba git


Big O Notation'─▒n ├žal─▒┼čma s├╝relerini ve itfa s├╝relerini ├Â─čreniyorum. O (n) lineer zaman kavram─▒n─▒ anl─▒yorum , yani giri┼čin b├╝y├╝kl├╝─č├╝ algoritman─▒n b├╝y├╝mesini orant─▒l─▒ olarak etkiliyor ... ve ayn─▒, ├Ârne─čin, ikinci dereceden O (n 2 ) vb. ├Ârne─čin , factorials taraf─▒ndan b├╝y├╝yen O (n!) zamanlar─▒ olan perm├╝tasyon jenerat├Ârleri gibi .

├ľrne─čin, a┼ča─č─▒daki i┼člev O (n) 'dir, ├ž├╝nk├╝ algoritma n giri┼či ile orant─▒l─▒ olarak b├╝y├╝r :

 f(int n) {
  int i;
  for (i = 0; i < n; ++i)
    printf("%d", i);
}
 

Benzer ┼čekilde, i├ž i├že ge├žmi┼č bir d├Âng├╝ olsayd─▒, zaman O (n 2 ) olurdu .

Ama tam olarak O (log n) nedir? ├ľrne─čin, tam bir ikili a─čac─▒n y├╝ksekli─činin O (log n) oldu─čunu s├Âylemek ne anlama gelir ?

Logaritman─▒n ne oldu─čunu (belki de ayr─▒nt─▒l─▒ bir ┼čekilde bilmiyor olabilirim) biliyorum, yani: log 10 100 = 2, ancak logaritmik bir zaman ile bir fonksiyonu nas─▒l tan─▒mlayaca─č─▒m─▒ anlayam─▒yorum.


1979









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






G├╝nl├╝k zaman─▒yla bir i┼člevi nas─▒l tan─▒mlayaca─č─▒m─▒ anlayam─▒yorum.

Logaritmik ├žal─▒┼čma zaman─▒ fonksiyonunun en yayg─▒n ├Âzellikleri ┼čunlard─▒r:

  • Bir eylemin ger├žekle┼čtirilece─či bir sonraki eleman─▒n se├žimi, birka├ž olas─▒l─▒ktan biridir ve
  • sadece birinin se├žilmesi gerekecek.

veya

  • eylemin ger├žekle┼čtirildi─či ├Â─čeler n'nin rakamlar─▒d─▒r.

Bu nedenle, ├Ârne─čin bir telefon rehberindeki insanlar─▒ aramak O (log n). Do─čru ki┼čiyi bulmak i├žin telefon rehberindeki her ki┼čiyi kontrol etmeniz gerekmez ; bunun yerine, adlar─▒n─▒n alfabetik olarak bulundu─ču yere bakarak kolayca b├Âl├╝nebilir ve ele ge├žirilebilir ve her b├Âl├╝mde eninde sonunda birisinin telefon numaras─▒n─▒ bulmadan ├Ânce her b├Âl├╝m├╝n bir alt k├╝mesini ke┼čfetmeniz gerekir.

Tabii ki, daha b├╝y├╝k bir telefon rehberi size daha uzun s├╝rebilir, ancak ek boyuttaki orant─▒l─▒ art─▒┼č kadar h─▒zl─▒ b├╝y├╝meyecektir.


Biz operasyonlar─▒n di─čer t├╝r ve kar┼č─▒la┼čt─▒rmak i├žin telefon rehberi ├Ârne─či geni┼čletebilirsiniz onlar─▒n ├žal─▒┼čma s├╝resi. Telefon defterimizde benzersiz adlara sahip olmayan i┼čletmelere ("Sar─▒ Sayfalar") ve benzersiz adlara sahip olmayan insanlara ("Beyaz Sayfalar") sahip olaca─č─▒m─▒z─▒ varsayaca─č─▒z . Bir telefon numaras─▒ en fazla bir ki┼čiye veya i┼čletmeye atan─▒r. Ayr─▒ca belirli bir sayfaya ├ževirmenin zaman ald─▒─č─▒n─▒ da varsayaca─č─▒z.

Telefon rehberinde ger├žekle┼čtirebilece─čimiz baz─▒ i┼člemlerin ├žal─▒┼čma s├╝releri, en iyiden en k├Ât├╝ye do─čru:

  • O (1) (en iyi durum): Bir i┼čletme ad─▒n─▒n a├ž─▒k oldu─ču sayfa ve i┼čletme ad─▒ verilen telefon numaras─▒n─▒ bulun.

  • O (1) (ortalama durum): Bir ki┼činin isminin a├ž─▒k oldu─ču sayfa ve isminde, telefon numaras─▒n─▒ bulun.

  • O (log n): Bir ki┼činin ad─▒ verildi─činde, hen├╝z aramad─▒─č─▒n─▒z kitab─▒n yar─▒s─▒ boyunca rastgele bir nokta se├žerek telefon numaras─▒n─▒ bulun ve ard─▒ndan ki┼činin ad─▒n─▒n o noktada olup olmad─▒─č─▒n─▒ kontrol edin. Ard─▒ndan, ki┼činin ad─▒n─▒n bulundu─ču kitab─▒n yar─▒s─▒na kadar olan s├╝reci tekrarlay─▒n. (Bu, bir ki┼činin ad─▒ i├žin yap─▒lan ikili aramad─▒r.)

  • O (n): Telefon numaralar─▒ "5" rakam─▒n─▒ i├žeren t├╝m ki┼čileri bul.

  • O (n): Bir telefon numaras─▒ verildi─činde, bu numaraya sahip ki┼čiyi veya i┼čletmeyi bulun.

  • O (n log n): Yaz─▒c─▒n─▒n ofisinde karma┼ča vard─▒ ve telefon rehberimiz t├╝m sayfalar─▒n─▒ rasgele bir s─▒rayla yerle┼čtirdi. Sipari┼či, her sayfadaki ilk ad─▒ izleyerek ve ard─▒ndan bu sayfay─▒ yeni ve bo┼č bir telefon rehberinde uygun noktaya koyarak do─čru ┼čekilde d├╝zeltin.

A┼ča─č─▒daki ├Ârnekler i├žin, ┼čimdi yaz─▒c─▒n─▒n ofisindeyiz. Telefon rehberleri her ikamet veya i┼čletmeye postalanmay─▒ bekliyor ve her telefon defterinde nereye g├Ânderilece─čini belirten bir ├ž─▒kartma var. Her insan veya i┼č bir telefon rehberi al─▒r.

  • O (n log n): Telefon rehberini ki┼čiselle┼čtirmek istiyoruz, bu nedenle her bir ki┼činin veya i┼čletmenin ad─▒n─▒ belirlenmi┼č kopyalar─▒nda bulaca─č─▒z, sonra isimlerini kitapta daire i├žine alaca─č─▒z ve patronaj─▒ i├žin k─▒sa bir te┼čekk├╝r notu yazaca─č─▒z. .

  • S (n 2 ): Ofiste bir hata olu┼čtu ve telefon rehberlerinin her giri┼činde telefon numaras─▒n─▒n sonunda fazladan "0" var. Biraz beyazl─▒k al─▒n ve her s─▒f─▒r─▒ kald─▒r─▒n.

  • O (n ┬Ě n!): Telefon rehberlerini sevkiyat istasyonuna y├╝klemeye haz─▒r─▒z. Ne yaz─▒k ki, kitaplar─▒ y├╝klemesi gereken robotlar haydi tel├ófi oldu: kitaplar─▒ rasgele bir s─▒raya sokuyor! Daha da k├Ât├╝s├╝, b├╝t├╝n kitaplar─▒ istif arac─▒na y├╝kler, ard─▒ndan do─čru s─▒rada olup olmad─▒klar─▒n─▒ kontrol eder ve e─čer de─čilse bo┼čalt─▒r ve ba┼čtan ba┼člar. (Bu korkun├ž bogo t├╝r .)

  • O (n n ): Robotu, i┼čleri do─čru bir ┼čekilde y├╝kleyecek ┼čekilde sabitlediniz. Ertesi g├╝n, i┼č arkada┼člar─▒n─▒zdan biri size bir ┼čaka yap─▒yor ve y├╝kleme iskelesi robotunu otomatik bask─▒ sistemlerine ba─čl─▒yor. Robot orijinal bir kitab─▒ her y├╝kledi─činde, fabrika yaz─▒c─▒s─▒ t├╝m telefon rehberlerinin ├žo─čunu ├žal─▒┼čt─▒r─▒yor! Neyse ki, robotun hata tespit sistemleri, y├╝klenecek yinelenen bir kitapla kar┼č─▒la┼čt─▒─č─▒nda, robotun daha fazla kopya basmay─▒ denemeyece─či kadar karma┼č─▒kt─▒r, ancak yazd─▒r─▒lan her orijinal ve yinelenen kitab─▒ y├╝klemesi gerekir.

Daha fazla matematiksel a├ž─▒klama i├žin zaman karma┼č─▒kl─▒─č─▒n─▒n log n buraya nas─▒l geldi─čini kontrol edebilirsiniz . https://hackernoon.com/what-does-the-time-complexity-o-log-n-actually-mean-45f94bb5bfbf


2524







Bu soruya ├žok say─▒da iyi cevap g├Ânderildi, ancak ├Ânemli bir cevab─▒ - yani resimli cevab─▒ ├Âzledi─čimize inan─▒yorum.

Tam bir ikili a─čac─▒n y├╝ksekli─činin O (log n) oldu─čunu s├Âylemek ne anlama gelir?

A┼ča─č─▒daki ├žizim bir ikili a─čac─▒ g├Âstermektedir. Her seviyenin yukar─▒daki seviyeye k─▒yasla iki kat d├╝─č├╝m i├žerdi─čine dikkat edin (bu nedenle ikili ):


─░kili a─ča├ž

─░kili arama, karma┼č─▒kl─▒─č─▒ g├Âsteren bir ├Ârnektir O(log n) . Diyelim ki, ┼×ekil 1'deki a─čac─▒n alt seviyesindeki d├╝─č├╝mlerin baz─▒ s─▒ralanm─▒┼č koleksiyonlardaki ├Â─čeleri temsil etti─čini varsayal─▒m. ─░kili arama, bir b├Âl ve ele ge├žir algoritmas─▒d─▒r ve ├žizim bu 16 madde veri setinde arad─▒─č─▒m─▒z kayd─▒ bulmak i├žin nas─▒l (en fazla) 4 kar┼č─▒la┼čt─▒rmaya ihtiyac─▒m─▒z olaca─č─▒n─▒ g├Âstermektedir.

Bunun yerine 32 elementli bir veri setine sahip oldu─čumuzu varsayal─▒m. A─ča├ž, veri miktar─▒n─▒ ├žarpt─▒─č─▒m─▒zda yaln─▒zca bir seviye daha derinle┼čti─činden, arad─▒─č─▒m─▒z─▒ bulmak i├žin ┼čimdi 5 kar┼č─▒la┼čt─▒rmaya ihtiyac─▒m─▒z olaca─č─▒n─▒ bulmak i├žin yukar─▒daki ├žizime devam edin. Sonu├ž olarak, algoritman─▒n karma┼č─▒kl─▒─č─▒ logaritmik bir d├╝zen olarak tan─▒mlanabilir.

log(n) D├╝z bir ka─č─▒da ├žizilmesi , e─črinin y├╝kseli┼činin n artt─▒k├ža azald─▒─č─▒ bir grafikle sonu├žlanacakt─▒r :


O (log n)


553







O(log N) temel olarak, zaman n katlanarak artar, ├╝stel olarak katlan─▒r. Tek gereken Yani e─čer 1 hesaplama ikinci 10 elemanlar─▒n, s├╝rer 2 hesaplamak saniye 100 elemanlar─▒, 3 saniye hesaplama i├žin 1000 benzeri unsurlar─▒n, vb.

├ľyle O(log n) biz Algoritmalar─▒n ├Ârne─čin ikili arama b├Âlmek ve fethetmek t├╝r├╝ bir s├Âz vard─▒r. Di─čer bir ├Ârnek, diziyi iki par├žaya b├Âld├╝─č├╝m├╝z ve O(N) bir pivot eleman─▒ bulmak i├žin her zaman harcad─▒─č─▒m─▒z h─▒zl─▒ s─▒ralamad─▒r . Dolay─▒s─▒yla N O(log N)


543







A┼ča─č─▒daki a├ž─▒klama logaritmik zaman karma┼č─▒kl─▒─č─▒n─▒ nas─▒l elde etti─čimizi anlaman─▒za yard─▒mc─▒ olmak i├žin tamamen dengeli bir ikili a─ča├ž kasas─▒ kullanmaktad─▒r .

─░kili a─ča├ž n b├╝y├╝kl├╝─č├╝nde bir problemin 1/2 boyutuna ula┼čana kadar n / 2 boyutunda alt probleme b├Âl├╝nd├╝─č├╝ bir durumdur:


bir ikili a─čac─▒n y├╝ksekli─či

Ve bir ├ž├Âz├╝m elde etmek i├žin yukar─▒daki a─ča├ž ├╝zerinde yap─▒lmas─▒ gereken i┼čin miktar─▒ olan O (log n) bu ┼čekilde elde edilir.

O (log n) zaman karma┼č─▒kl─▒─č─▒na sahip ortak bir algoritma, ├Âzyinelemeli ili┼čkisi T (n / 2) + O (1) olan ─░kili Arama'd─▒r, yani a─čac─▒n sonraki her seviyesinde problemi ikiye b├Âler ve sabit miktarda ek i┼č yapars─▒n─▒z.


228







genel bak─▒┼č

Di─čerleri, a─ča├ž diyagramlar─▒ gibi iyi diyagram ├Ârnekleri vermi┼čtir. Basit bir kod ├Ârne─či g├Ârmedim. Bu y├╝zden a├ž─▒klamama ek olarak, farkl─▒ algoritma kategorilerinin karma┼č─▒kl─▒─č─▒n─▒ g├Âstermek i├žin basit bask─▒ ifadeleri i├žeren baz─▒ algoritmalar sa─člayaca─č─▒m.

├ľncelikle, https://en.wikipedia.org/wiki/Logarithm adresinden alabilece─činiz genel bir Logaritma fikrine sahip olmak isteyeceksiniz . Do─čal bilim kullan─▒m─▒ e ve do─čal k├╝t├╝k. M├╝hendislik ├Â─črencileri log_10 (log base 10) kullan─▒rlar ve bilgisayar bilimcileri log_2 (log base 2) ├žok kullan─▒rlar, ├ž├╝nk├╝ bilgisayarlar ikili tabanl─▒d─▒r. Bazen do─čal k├╝t├╝─č├╝n k─▒saltmas─▒n─▒ g├Âr├╝rs├╝n├╝z ln() , m├╝hendisler normalde _10'u b─▒rak─▒r ve sadece kullan─▒r log() ve log_2 k─▒salt─▒l─▒r lg() . T├╝m logaritma t├╝rleri benzer ┼čekilde b├╝y├╝r, bu y├╝zden ayn─▒ kategoriyi payla┼č─▒rlar log(n) .

A┼ča─č─▒daki kod ├Ârneklerine bakt─▒─č─▒n─▒zda, O (1), sonra O (n), sonra O (n ^ 2) 'ye bakman─▒z─▒ ├Âneririm. Bunlar─▒ iyi yapt─▒ktan sonra di─čerlerine bak─▒n. ─░nce ├Ârneklerin nas─▒l ayn─▒ kategorile┼čtirmeyle sonu├žlanabilece─čini g├Âsteren de─či┼čikliklerin yan─▒ s─▒ra temiz ├Ârnekler de dahil ettim.

O (1), O (n), O (logn) vb. S─▒n─▒flar─▒ veya b├╝y├╝me kategorileri olarak d├╝┼č├╝nebilirsiniz. Baz─▒ kategorilerin yap─▒lmas─▒ di─čerlerinden daha fazla zaman alacakt─▒r. Bu kategoriler bize algoritma performans─▒n─▒ s─▒ralaman─▒n bir yolunu sunar. Baz─▒lar─▒ n b├╝y├╝d├╝k├že daha h─▒zl─▒ b├╝y├╝r. A┼ča─č─▒daki tablo, s├Âz konusu b├╝y├╝meyi say─▒sal olarak g├Âstermektedir. A┼ča─č─▒daki tabloda log'u (n) log_2'nin tavan─▒ olarak d├╝┼č├╝n├╝n.


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

├çe┼čitli B├╝y├╝k O Kategorileri Basit Kod ├ľrnekleri:

O (1) - Sabit Zamanl─▒ ├ľrnekler:

  • Algoritma 1:

Algoritma 1 bir kez merhaba yazd─▒r─▒r ve n'e ba─čl─▒ de─čildir, bu y├╝zden her zaman sabit zamanda ├žal─▒┼čacakt─▒r, ├Âyledir O(1) .

 print "hello";
 
  • Algoritma 2:

Algoritma 2, 3 kez merhaba yazd─▒r─▒r, ancak giri┼č boyutuna ba─čl─▒ de─čildir. N b├╝y├╝d├╝k├že bile, bu algoritma her zaman sadece 3 kez merhaba yazd─▒racak. Bunun s├Âylenmesi 3, bir sabittir, bu y├╝zden bu algoritma da ├Âyle O(1) .

 print "hello";
print "hello";
print "hello";
 

O (log (n)) - Logaritmik ├ľrnekler:

  • Algoritma 3 - Bu "log_2" gibi davran─▒r

Algoritma 3, log_2 (n) 'de ├žal─▒┼čan bir algoritmay─▒ g├Âsterir. For d├Âng├╝s├╝n├╝n g├Ânderim i┼čleminin i'nin ┼ču anki de─čerini 2'ye i katlad─▒─č─▒na dikkat edin , bu nedenle 1'den 2'ye 4 ila 8'den 16'ya 32 ...

 for(int i = 1; i <= n; i = i * 2)
  print "hello";
 
  • Algoritma 4 - "log_3" gibi davran─▒r

Algoritma 4 log_3'├╝ g├Âstermektedir. Uyar─▒ i 1'den 3'e, 9'dan 27'ye ...

 for(int i = 1; i <= n; i = i * 3)
  print "hello";
 
  • Algoritma 5 - "log_1.02" gibi davran─▒r

Algoritma 5, say─▒n─▒n 1'den b├╝y├╝k oldu─ču ve sonucun kendisiyle tekrar tekrar ├žarp─▒ld─▒─č─▒, logaritmik bir algoritmaya bakt─▒─č─▒n─▒z─▒ g├Âsterdi─či i├žin ├Ânemlidir.

 for(double i = 1; i < n; i = i * 1.02)
  print "hello";
 

O (n) - Do─črusal Zaman ├ľrnekleri:

  • Algoritma 6

Bu algoritma basittir, merhaba n kere basar.

 for(int i = 0; i < n; i++)
  print "hello";
 
  • Algoritma 7

Bu algoritma, 2 kez merhaba yazaca─č─▒ bir varyasyon g├Âsterir. n / 2 = 1/2 * n. 1/2 sabiti yok sayar ve bu algoritman─▒n O (n) oldu─čunu g├Âr├╝r├╝z.

 for(int i = 0; i < n; i = i + 2)
  print "hello";
 

O (n * log (n)) - nlog (n) ├ľrnekler:

  • Algoritma 8

Bir kombinasyonu olarak d├╝┼č├╝n├╝n O(log(n)) ve O(n) . For d├Âng├╝lerinin i├ž i├že ge├žmesi bize O(n*log(n))

 for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";
 
  • Algoritma 9

Algoritma 9, algoritma 8 gibidir, ancak d├Âng├╝lerin her biri, nihai sonucun ortaya ├ž─▒kmas─▒na neden olan varyasyonlara izin vermi┼čtir. O(n*log(n))

 for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";
 

O (n ^ 2) - n kare ├ľrnekler:

  • Algoritma 10

O(n^2) D├Âng├╝ler i├žin standart yuvalama yoluyla kolayca elde edilir.

 for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";
 
  • Algoritma 11

Algoritma 10 gibi, ama baz─▒ de─či┼čimlerle.

 for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";
 

O (n ^ 3) - n ku┼čba┼č─▒ ├ľrnekler:

  • Algoritma 12

Bu, algoritma 10'a benzer, ancak 2 yerine 3 d├Âng├╝l├╝d├╝r.

 for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";
 
  • Algoritma 13

Algoritma 12 gibi, ama yine de verim baz─▒ varyasyonlar─▒ ile O(n^3) .

 for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";
 

├Âzet

Yukar─▒dakiler, birka├ž basit ileri ├Ârnek vermekte ve analizi ger├žekten de─či┼čtirmeyen hangi ince de─či┼čikliklerin ortaya ├ž─▒kabilece─čini g├Âstermeye yard─▒mc─▒ olacak varyasyonlar vermektedir. Umar─▒m size yeterince bilgi verir.


164







E─čer bir i┼člevi varsa ald─▒:

 1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2**n elements.
 

Sonra log 2 (n) zaman al─▒r. B├╝y├╝k O g├Âsterimi , gev┼ček ili┼čki sadece b├╝y├╝k n i├žin ger├žek olmas─▒ gerekti─čini, arac─▒ konu┼čan ve bu sabit fakt├Ârleri ve daha k├╝├ž├╝k terimler g├Âz ard─▒ edilebilir.


127







Logaritmik ├žal─▒┼čma s├╝resi ( O(log n) ), esasen, ├žal─▒┼čma s├╝resinin , girdi b├╝y├╝kl├╝─č├╝n├╝n logaritmas─▒ ile orant─▒l─▒ olarak b├╝y├╝d├╝─č├╝ anlam─▒na gelir - bir ├Ârnek olarak, e─čer 10 ├Â─če en fazla zaman al─▒rsa x ve 100 ├Â─če en fazla, yani 2x ve 10.000 ├Â─če al─▒rsa en fazla 4x zaman al─▒r , o O(log n) zaman zaman karma┼č─▒kl─▒─č─▒na benziyor .


92







Logaritma

Tamam, hadi bir logaritman─▒n ger├žekte ne oldu─čunu anlamaya ├žal─▒┼čal─▒m.

Bir ipimiz oldu─čunu ve onu bir ata ba─člad─▒─č─▒m─▒z─▒ hayal edin. E─čer halat do─črudan ata ba─čl─▒ysa, at─▒n ├žekmesi gereken kuvvet (├Ârne─čin, bir erkekten) do─črudan 1'dir.

┼×imdi ipin bir kutup etraf─▒nda dola┼čt─▒─č─▒n─▒ hayal edin. Ka├žmak i├žin at ┼čimdi bir├žok kez daha zor ├žekmek zorunda kalacak. S├╝relerin miktar─▒, ipin p├╝r├╝zl├╝l├╝─č├╝ne ve dire─čin boyutuna ba─čl─▒ olacakt─▒r, ancak bunun kuvvetini 10 ile ├žarpaca─č─▒n─▒ varsayal─▒m (ip tam bir d├Ân├╝┼č yapt─▒─č─▒nda).

┼×imdi ip bir kez ilmeklenirse, at─▒n 10 kat daha sert ├žekilmesi gerekir. E─čer insan at i├žin ger├žekten zorla┼čmaya karar verirse, ipi bir dire─če tekrar sokarak g├╝c├╝n├╝ 10 kat art─▒rabilir. ├ť├ž├╝nc├╝ bir d├Âng├╝, g├╝c├╝ tekrar 10 kat daha art─▒racakt─▒r.


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

Her d├Âng├╝ i├žin de─čerin 10 artt─▒─č─▒n─▒ g├Ârebiliyoruz. Herhangi bir say─▒y─▒ almak i├žin gereken sar─▒m say─▒s─▒, say─▒n─▒n logaritmas─▒ olarak adland─▒r─▒l─▒r, yani g├╝c├╝n├╝z├╝ ├žarp─▒m─▒n─▒ ├žarpmak i├žin g├╝c├╝n├╝z├╝ 1000 kat katlamas─▒ i├žin 3 yaz─▒ya, 6 yaz─▒y─▒ ├žarpman─▒z gerekir. 1,000,000.

┼×ekil 3, 1.000'in logaritmas─▒d─▒r ve 6, 1.000.000'in logaritmas─▒d─▒r (taban 10).

Peki O (log n) asl─▒nda ne anlama geliyor?

Yukar─▒daki ├Ârne─čimizde, 'b├╝y├╝me oran─▒m─▒z' O (log n) . Her ek d├Âng├╝ i├žin, ipimizin kullanabilece─či kuvvet 10 kat daha fazla:

 Turns | Max Force
  0   |   1
  1   |   10
  2   |   100
  3   |   1000
  4   |   10000
  n   |   10^n
 

┼×imdi yukar─▒daki ├Ârnek 10 taban─▒n─▒ kulland─▒, ama neyse ki b├╝y├╝k notasyondan bahsetti─čimizde k├╝t├╝─č├╝n taban─▒ ├Ânemsiz.

┼×imdi, 1-100 aras─▒nda bir say─▒ tahmin etmeye ├žal─▒┼čt─▒─č─▒n─▒z─▒ d├╝┼č├╝nelim.

 Your Friend: Guess my number between 1-100! 
Your Guess: 50
Your Friend: Lower!
Your Guess: 25
Your Friend: Lower!
Your Guess: 13
Your Friend: Higher!
Your Guess: 19
Your Friend: Higher!
Your Friend: 22
Your Guess: Lower!
Your Guess: 20
Your Friend: Higher!
Your Guess: 21
Your Friend: YOU GOT IT!  
 

┼×imdi bunu do─čru yapmak i├žin 7 tahmin ald─▒. Fakat buradaki ili┼čki nedir? Her ek tahminde tahmin edebilece─činiz en fazla kalem nedir?

 Guesses | Items
  1     |   2
  2     |   4
  3     |   8
  4     |   16
  5     |   32
  6     |   64
  7     |   128
  10    |   1024
 

Grafi─či kullanarak, 1-100 aras─▒nda bir say─▒ tahmin etmek i├žin ikili bir arama kullan─▒rsak, bizi en fazla 7 deneme alaca─č─▒n─▒ g├Ârebiliriz . 128 say─▒ olsayd─▒, ayn─▒ zamanda 7 tav─▒rdaki say─▒y─▒ da tahmin edebilirdik, ancak 129 say─▒ bizi en fazla 8 deneme yapacakt─▒r (logaritma ile ilgili olarak, burada 128 de─čer aral─▒─č─▒ i├žin 7 tahmin, 1024 de─čer aral─▒─č─▒ i├žin 10 tahmin) 7, 128 logaritmas─▒d─▒r, 10, 1024 logaritmas─▒d─▒r (temel 2).

'En fazla' kal─▒n oldu─čuna dikkat edin. B├╝y├╝k g├Âsterim, her zaman en k├Ât├╝ durumu ifade eder. ┼×ansl─▒ysan─▒z, say─▒y─▒ bir denemede tahmin edebilirsiniz ve bu nedenle en iyi durum O (1), ama bu ba┼čka bir hikaye.

Her tahmin i├žin veri setimizin k├╝├ž├╝ld├╝─č├╝n├╝ g├Ârebiliyoruz. Bir algoritman─▒n logaritmik bir s├╝reye sahip olup olmad─▒─č─▒n─▒ belirlemek i├žin iyi bir kural, veri k├╝mesinin her bir yinelemeden sonra belirli bir d├╝zende k├╝├ž├╝l├╝p k├╝├ž├╝lmedi─čini g├Ârmektir.

Peki ya O (n log n)?

Sonunda bir linerarithmic zaman rastlamak olacakt─▒r n log (n) (O yine ge├žerlidir yukar─▒da. Algoritmas─▒ ba┼čparmak ├╝st├╝nl├╝─č├╝, ancak logaritmik fonksiyon n kere mesela bir liste boyutunu k├╝├ž├╝ltmeyi ├žal─▒┼čt─▒rmak zorundad─▒r bu sefer n kez algoritmalar─▒ olu┼čur, Mergesort gibi.

Algoritmik zaman─▒n n log n olup olmad─▒─č─▒n─▒ kolayca belirleyebilirsiniz. Listede yinelenen bir d─▒┼č d├Âng├╝ aray─▒n (O (n)). Sonra bir i├ž d├Âng├╝ olup olmad─▒─č─▒n─▒ g├Ârmek i├žin bak─▒n. ─░├ž d├Âng├╝, her yinelemede ayarlanan verileri kesiyor / azalt─▒yorsa , bu d├Âng├╝ (O (log n)) ve genel algoritma = O (n log n) olur .

Feragatname: Halat logaritmas─▒ ├Ârne─či, W. Materatician'─▒n Delight kitab─▒ndan W.Sawyer'den al─▒nm─▒┼čt─▒r .


77







O zaman─▒ (log N) sezgisel olarak zaman─▒n N'deki hane say─▒s─▒ ile orant─▒l─▒ oldu─čunu s├Âyleyerek d├╝┼č├╝nebilirsiniz.

Bir i┼člem bir giri┼čin her bir basama─č─▒n─▒n veya bitinin ├╝zerinde sabit zaman ├žal─▒┼čmas─▒ ger├žekle┼čtirirse, t├╝m i┼člem giri┼čin b├╝y├╝kl├╝─č├╝n├╝ de─čil, giri┼č i├žindeki basamak veya bitlerin say─▒s─▒yla orant─▒l─▒ olarak zaman al─▒r; B├Âylece, O (N) yerine O (log N).

Bir i┼člem, dikkate al─▒nacak girdinin b├╝y├╝kl├╝─č├╝n├╝ yar─▒ya indiren (3, 4, 5 .. bir fakt├Ârle azal─▒r) bir dizi sabit zaman karar─▒n─▒ verirse, b├╝t├╝n, k├╝t├╝k baz 2 (baz 3) ile orant─▒l─▒ olarak zaman alacakt─▒r. , taban 4, taban 5 ...) O (N) olmak yerine giri┼čin N boyutundad─▒r.

Ve bunun gibi.


56







Her zaman zihinsel olarak O (log n) 'de ├žal─▒┼čan bir algoritmay─▒ g├Ârselle┼čtirmek zorunda kalmam─▒n yolu:

Sorun boyutunu ├žoklay─▒c─▒ bir miktarda art─▒r─▒rsan─▒z (yani, boyutunu 10 ile ├žarp─▒n), i┼č yaln─▒zca ek bir miktarla art─▒r─▒l─▒r.

Bunu ikili a─ča├ž sorunuza uygulamak, b├Âylece iyi bir uygulaman─▒z olur: bir ikili a─ča├žtaki d├╝─č├╝m say─▒s─▒n─▒ iki kat─▒na ├ž─▒kar─▒rsan─▒z, y├╝kseklik yaln─▒zca 1 (ek bir miktar) artar. Tekrar ikiye katlarsan─▒z, yine de sadece 1 artar (A├ž─▒k├žas─▒, dengeli ve b├Âyle kald─▒─č─▒n─▒ varsay─▒yorum). Bu ┼čekilde, sorun b├╝y├╝kl├╝─č├╝ ile ├žarp─▒ld─▒─č─▒nda ├žal─▒┼čman─▒z─▒ ikiye katlamak yerine, sadece ├žok az i┼č yap─▒yorsunuz. Bu y├╝zden O (log n) algoritmalar─▒ harika.


51







─░lk ├Ânce a┼ča─č─▒daki kitab─▒ okuman─▒z─▒ tavsiye ederim;

Algoritmalar (4. Bask─▒)

─░┼čte baz─▒ fonksiyonlar ve beklenen karma┼č─▒kl─▒klar─▒. Say─▒lar, ifade y├╝r├╝tme frekanslar─▒n─▒ g├Âsterir .


─░┼čte baz─▒ fonksiyonlar ve beklenen karma┼č─▒kl─▒klar─▒

Big-O Karma┼č─▒kl─▒k Tablosunun ard─▒ndan bigocheatsheet'den al─▒nm─▒┼čt─▒r.http://bigocheatsheet.com/
B├╝y├╝k-O Karma┼č─▒kl─▒k Tablosu

Son olarak, ├žok basit bir vitrin, nas─▒l hesapland─▒─č─▒n─▒ g├Âsterir;

Bir program─▒n ifadesinin y├╝r├╝tme frekanslar─▒n─▒n anatomisi.

Bir program─▒n ├žal─▒┼čma zaman─▒n─▒ analiz etmek (├Ârnek).


Bir program─▒n ├žal─▒┼čma s├╝resini analiz etme


44







B g├╝nl├╝─č├╝ nedir (n)?

1 b├╝y├╝kl├╝─č├╝nde bir k─▒sma gelmeden ├Ânce, n uzunlu─čunu bir k├╝t├╝─č├╝ tekrar tekrar b e┼čit par├žaya kesebilece─činiz say─▒d─▒r.


42







B├Âlme ve fethetme algoritmalar─▒ genellikle logn ├žal─▒┼čma zaman─▒n─▒n bir bile┼čenine sahiptir. Bu, giri┼čin tekrarlanan yar─▒s─▒ndan gelir.

─░kili arama durumunda, giri┼čin yar─▒s─▒n─▒ att─▒─č─▒n─▒z her yineleme. Big-O notasyonunda logun log base 2 oldu─ču belirtilmelidir.

D├╝zenleme: Belirtildi─či gibi, log taban─▒ ├Ânemli de─čildir, ancak bir algoritman─▒n Big-O performans─▒n─▒ elde ederken, log fakt├Âr├╝ yar─▒dan gelecektir, bu y├╝zden bunu neden base 2 olarak d├╝┼č├╝n├╝yorum.


18







Ama tam olarak O (log n) nedir? ├ľrne─čin, bir> tam ikili a─čac─▒n y├╝ksekli─činin O (log n) oldu─čunu s├Âylemek ne anlama gelir?

Bunu 'tam bir ikili a─čac─▒n y├╝ksekli─či log n'dir' olarak de─či┼čtirirdim. Tam bir ikili a─čac─▒n y├╝ksekli─čini bulmak, e─čer ad─▒m ad─▒m a┼ča─č─▒ do─čru hareket ediyorsan─▒z, O (log n) olacakt─▒r.

Logaritmik bir zaman ile bir fonksiyonu nas─▒l tan─▒mlayaca─č─▒m─▒ anlayam─▒yorum.

Logaritma temel olarak ├╝stelle┼čtirmenin tersidir. Bu nedenle, fonksiyonunuzun her bir ad─▒m─▒ orijinal ├Â─če setinden bir ├Â─če fakt├Âr├╝n├╝ ortadan kald─▒r─▒yorsa , bu logaritmik bir zaman algoritmas─▒d─▒r.

A─ča├ž ├Ârne─činde, bir d├╝─č├╝m seviyesini d├╝┼č├╝rmenin, ge├ži┼če devam ederken ├╝ssel bir ├Â─če say─▒s─▒n─▒ azaltt─▒─č─▒n─▒ kolayca g├Ârebilirsiniz. Adl─▒ bir telefon rehberine bakman─▒n pop├╝ler ├Ârne─či, esas olarak ikili bir arama a─čac─▒n─▒ a┼ča─č─▒ do─čru kayd─▒rmaya e┼čde─čerdir (orta sayfa k├Âk ├Â─čedir ve her ad─▒mda sola veya sa─ča gitmek isteyip istemedi─činizi saptayabilirsiniz).


15







Bu 2 vaka O (log n) zaman alacak

 case 1: f(int n) {
      int i;
      for (i = 1; i < n; i=i*2)
        printf("%d", i);
    }


 case 2  : f(int n) {
      int i;
      for (i = n; i>=1 ; i=i/2)
        printf("%d", i);
    }
 

12







O(log n) logaritma ile orant─▒l─▒ bir s├╝rede ├žal─▒┼čan bir fonksiyon (veya algoritma veya bir algoritmadaki ad─▒m) anlam─▒na gelir (├žo─ču durumda genellikle taban 2, ancak her zaman de─čil, ve her durumda bu b├╝y├╝k O notasyonu ile ├Ânemsizdir) * Giri┼čin b├╝y├╝kl├╝─č├╝.

Logaritmik fonksiyon, ├╝stel fonksiyonun tersidir. Ba┼čka bir deyi┼čle, giri┼činiz katlanarak b├╝y├╝rse (normal olarak d├╝┼č├╝nd├╝─č├╝n├╝z gibi do─črusal de─čil), i┼čleviniz do─črusal olarak b├╝y├╝r.

O(log n) ├žal─▒┼čma s├╝releri, herhangi bir b├Âl ve ele ge├žir uygulamas─▒nda ├žok yayg─▒nd─▒r, ├ž├╝nk├╝ i┼či her seferinde yar─▒ya indirdi─činizden (ideal). Her bir b├Âl├╝nme veya fethetme ad─▒mlar─▒n─▒n her birinde, sabit zamanl─▒ ├žal─▒┼čma yap─▒yorsunuz (veya sabit zamanl─▒ olmayan, ancak zamandan daha yava┼č b├╝y├╝yorsa O(log n) ), o zaman t├╝m fonksiyonunuz O(log n) . Her bir ad─▒m─▒n giri┼čte do─črusal zaman gerektirmesi olduk├ža yayg─▒nd─▒r; bu, toplam zaman karma┼č─▒kl─▒─č─▒ anlam─▒na gelecektir O(n log n) .

─░kili araman─▒n ├žal─▒┼čma s├╝resi karma┼č─▒kl─▒─č─▒na bir ├Ârnek O(log n) . Bunun nedeni, ikili aramada, her sonraki ad─▒mda giri┼činizin yar─▒s─▒n─▒ her zaman g├Ârmezden geldi─činizden, diziyi yar─▒ya b├Âlerek ve her ad─▒mda yaln─▒zca bir yar─▒ya odaklanman─▒zd─▒r. Her ad─▒m sabit zamanl─▒d─▒r, ├ž├╝nk├╝ ikili aramada, d├╝┼č├╝nd├╝─č├╝n├╝z dizinin herhangi bir noktada ne kadar b├╝y├╝k oldu─čuna bak─▒lmaks─▒z─▒n ne yapaca─č─▒n─▒z─▒ bulmak i├žin anahtar─▒n─▒zla yaln─▒zca bir ├Â─čeyi kar┼č─▒la┼čt─▒rman─▒z gerekir. B├Âylece yakla┼č─▒k log (n) / log (2) ad─▒mlar─▒n─▒ uygulars─▒n─▒z.

Birle┼čtirme s─▒ralama ├žal─▒┼čma s├╝resi karma┼č─▒kl─▒─č─▒ bir ├Ârnektir O(n log n) . Bunun nedeni, diziyi her ad─▒mla ikiye b├Âlmek ve toplamda yakla┼č─▒k log (n) / log (2) ad─▒mlar─▒n─▒n olu┼čmas─▒d─▒r. Ancak, her ad─▒mda t├╝m ├Â─čelerde birle┼čtirme i┼člemlerini ger├žekle┼čtirmeniz gerekir (bu, n / 2 ├Â─čenin iki alt listesindeki bir birle┼čtirme i┼člemi mi yoksa d├Ârt / 4 ├Â─čenin d├Ârt alt listesindeki iki birle┼čtirme i┼člemi ise, ilgisizdir ├ž├╝nk├╝ Bunu her ad─▒mda n elemanlar─▒ i├žin yap─▒n). B├Âylece, toplam karma┼č─▒kl─▒k O(n log n) .

* B├╝y├╝k O nota tan─▒m─▒n─▒ , tan─▒m olarak , sabitlerin ├Ânemli olmad─▒─č─▒n─▒ unutmay─▒n. Ayr─▒ca logaritmalar i├žin baz kural─▒n─▒n de─či┼čtirilmesiyle, farkl─▒ bazlar─▒n logaritmalar─▒ aras─▒ndaki tek fark sabit bir fakt├Ârd├╝r.


10







O (log n) biraz yan─▒lt─▒c─▒d─▒r, daha do─črusu O (log 2 n), yani (baz 2 ile logaritma).

Dengeli bir ikili a─čac─▒n y├╝ksekli─či O (log 2 n), ├ž├╝nk├╝ her d├╝─č├╝mde iki (log 2 n'deki "iki" ye dikkat edin ) alt d├╝─č├╝mler var. Bu nedenle, d├╝─č├╝mleri olan bir a─čac─▒n k├╝t├╝─č├╝ 2 n'dir.

Di─čer bir ├Ârnek de O (log 2 n) ├žal─▒┼čma s├╝resi olan ikili aramad─▒r ├ž├╝nk├╝ her ad─▒mda arama alan─▒n─▒ 2'ye b├Âlersiniz.


10







Bu sadece bu g├Ârev i├žin gereken zaman─▒n log (n) ile b├╝y├╝d├╝─č├╝ anlam─▒na gelir (├Ârnek: n = 10 i├žin 2s, n = 100 i├žin ..., ...). Daha fazla hassasiyet i├žin ─░kili Arama Algoritmas─▒ ve Big O Notasyonu hakk─▒ndaki Wikipedia makalelerini okuyun .


9







Basit├že s├Âylemek gerekirse: Algoritman─▒z─▒n her ad─▒m─▒nda i┼či ikiye b├Âlebilirsiniz. (Asimptotik olarak ├╝├ž├╝nc├╝, d├Ârd├╝nc├╝, ... ye e┼čde─čer)


9







Bir grafiksel hesap makinesine logaritmik bir i┼člev veya benzer bir ┼čey ├žizerseniz, bunun ger├žekten yava┼č├ža artt─▒─č─▒n─▒ g├Âreceksiniz - do─črusal bir i┼člevden bile daha yava┼č.

Bu nedenle logaritmik zaman karma┼č─▒kl─▒─č─▒na sahip algoritmalar ├žok aran─▒r: ger├žekten b├╝y├╝k n i├žin bile (├Ârne─čin n = 10 ^ 8 diyelim), kabul edilebilir bir ┼čekilde daha fazlas─▒n─▒ yaparlar.


8







Ama tam olarak ne O (log n)

Ne tam anlam─▒ "oldu─ču gibi n do─čru gitmektedir infinity , time do─čru e─čilimi a*log(n) nereye a sabit ├Âl├žekleme fakt├Âr├╝d├╝r".

Ya da asl─▒nda, bu tam olarak demek de─čildir; daha b├╝y├╝k olas─▒l─▒kla " time b├Âl├╝nme a*log(n) e─čiliminde " gibi bir ┼čey anlam─▒na gelir 1 .

'Analiz' dan ola─čan matematiksel anlama sahiptir "do─čru e─čilimindedir": "E─čer se├žerseniz, ├Ârne─čin bu herhangi keyfi k├╝├ž├╝k s─▒f─▒r olmayan sabit k , sonra kar┼č─▒l─▒k gelen de─čeri bulabilirsiniz X b├Âyle ((time/(a*log(n))) - 1) az oldu─ču k t├╝m de─čerleri i├žin n B├╝y├╝kt├╝r X ."


D├╝zensiz bir ifadeyle, zaman denkleminin ba┼čka baz─▒ bile┼čenlere sahip olabilece─či anlam─▒na gelir: ├Ârn. Baz─▒ sabit ba┼člang─▒├ž ÔÇőÔÇőzamanlar─▒na sahip olabilir; ancak bu di─čer bile┼čenler n'nin b├╝y├╝k de─čerleri i├žin ├Ânemsizli─če yol a├žar ve a * log (n) b├╝y├╝k n i├žin bask─▒n terimdir.

Denklem olsayd─▒, ├Ârne─čin ...

s├╝re (n) = a + b g├╝nl├╝─č├╝ (n) + c n + d n n

... o zaman bu O (n kare) olur ├ž├╝nk├╝ a, b, c ve s─▒f─▒r olmayan d sabitlerinin de─čerleri ne olursa olsun, d*n*n terim her zaman yeterince b├╝y├╝k n de─čeri i├žin di─čerlerine h├╝kmeder.

O bit notasyonunun anlam─▒ budur: "yeterince b├╝y├╝k n i├žin bask─▒n terimin s─▒ras─▒ nedir" anlam─▒na gelir.


7







Uzun zaman ├Ânce Kormen ve di─čerleri taraf─▒ndan kitapta okudum, ilgin├ž bir ┼čey ekleyebilirim. ┼×imdi, problem alan─▒nda bir ├ž├Âz├╝m bulmam─▒z gereken bir problem hayal edin. Bu problem alan─▒ sonlu olmal─▒d─▒r.

┼×imdi, e─čer algoritman─▒z─▒n her yinelemesinde, bu alan─▒n bir k─▒sm─▒n─▒ kesti─činizi, bir s─▒n─▒rdan daha az olmad─▒─č─▒n─▒ ispatlayabiliyorsan─▒z, bu, algoritman─▒z─▒n O (logN) zaman─▒nda ├žal─▒┼čt─▒─č─▒ anlam─▒na gelir.

Burada belirtmeliyim ki burada mutlak olandan de─čil, g├Âreceli bir kesir s─▒n─▒r─▒ndan bahsediyoruz. ─░kili arama klasik bir ├Ârnektir. Her ad─▒mda problemin 1 / 2'sini atar─▒z. Ancak bu ikili ├Ârnek ikili arama de─čildir. Bir ┼čekilde, her ad─▒mda en az 1/128 problem alan─▒ att─▒─č─▒n─▒z─▒ kan─▒tlad─▒n─▒z. Bu, program─▒n─▒z hala ikili aramadan daha yava┼č olmas─▒na ra─čmen, O (logN) saatinde ├žal─▒┼č─▒yor demektir. ├ľzyinelemeli algoritmalar─▒n analizinde bu ├žok iyi bir ipucudur. Her ad─▒mda ├Âzyinelemenin birka├ž de─či┼čken kullanmayaca─č─▒ kan─▒tlanm─▒┼čt─▒r ve bu problem alan─▒nda baz─▒ kesirlerin kesilmesine yol a├žar.


7







Bir for d├Âng├╝s├╝ i├žin bir ├Ârnek verebilirim ve belki bir kez kavram─▒ kavrad─▒ belki farkl─▒ ba─člamlarda anla┼č─▒lmas─▒ daha kolay olur.

Bu, d├Âng├╝de ad─▒m─▒n katlanarak b├╝y├╝d├╝─č├╝ anlam─▒na gelir. ├ľrne─čin

 for (i=1; i<=n; i=i*2) {;}
 

Bu program─▒n O g├Âsteriminde karma┼č─▒kl─▒─č─▒ O (log (n)). Elle dola┼čmaya ├žal─▒┼čal─▒m (n, 512 ile 1023 aras─▒nda bir yerde olmak (1024 hari├ž):

 step: 1   2   3   4   5    6    7    8     9     10
   i: 1   2   4   8   16   32   64   128   256   512
 

N, 512 ile 1023 aras─▒nda bir yerde olmas─▒na ra─čmen, sadece 10 yineleme ger├žekle┼čir. Bunun nedeni d├Âng├╝deki ad─▒m─▒n katlanarak b├╝y├╝mesi ve bu nedenle sonland─▒rmaya ula┼čmak i├žin yaln─▒zca 10 yineleme gerektirmesidir.

X logaritmas─▒ (a'n─▒n taban─▒na), bir x'in tersi i┼člevidir.

Logaritman─▒n ├╝stelin tersi oldu─čunu s├Âylemek gibi bir ┼čey.

┼×imdi, bu ┼čekilde g├Ârmeye ├žal─▒┼č─▒n, e─čer ├╝stel ├žok h─▒zl─▒ b├╝y├╝rse, logaritma (ters) ├žok yava┼č b├╝y├╝r.

O (n) ve O (log (n)) aras─▒ndaki fark, O (n) ve O (a ^ n) (bir sabit) aras─▒ndaki farka benzer ┼čekilde b├╝y├╝kt├╝r.


6


2015-05-16





Ne zaman bir algoritma veya kod yazarsak, asimptotik karma┼č─▒kl─▒─č─▒n─▒ analiz etmeye ├žal─▒┼č─▒r─▒z. Zaman karma┼č─▒kl─▒─č─▒ndan farkl─▒d─▒r .

Asimptotik karma┼č─▒kl─▒k, bir algoritman─▒n y├╝r├╝tme zaman─▒n─▒n davran─▒┼č─▒, zaman karma┼č─▒kl─▒─č─▒ ise ger├žek y├╝r├╝tme zaman─▒d─▒r. Ancak baz─▒ insanlar bu terimleri birbirlerinin yerine kullan─▒r.

├ç├╝nk├╝ zaman karma┼č─▒kl─▒─č─▒ ├že┼čitli parametrelere ba─čl─▒ olarak de─či┼čebilir.
1. Fiziksel Sistem
2. Programlama Dili
3. Kodlama Stili
4. Ve daha fazlas─▒ ......

Ger├žek uygulama s├╝resi analiz i├žin iyi bir ├Ânlem de─čildir.


Bunun yerine girdi boyutunu parametre olarak al─▒r─▒z, ├ž├╝nk├╝ kod ne olursa olsun, girdi ayn─▒d─▒r. Yani y├╝r├╝tme s├╝resi, giri┼č boyutunun bir fonksiyonudur.

A┼ča─č─▒daki Do─črusal Zaman Algoritmas─▒n─▒n bir ├Ârne─čidir


Do─črusal Arama
Verilen n girdi eleman─▒, dizideki bir eleman─▒ aramak i├žin en ├žok 'n' kar┼č─▒la┼čt─▒rmas─▒na ihtiyac─▒n─▒z var . Ba┼čka bir deyi┼čle, hangi programlama dilini kullan─▒rsan─▒z kullan─▒n, hangi kodlama stilini tercih ederseniz edin, hangi sistemi uygularsan─▒z uygulay─▒n. En k├Ât├╝ senaryoda, sadece n kar┼č─▒la┼čt─▒rmas─▒ gerekir. Uygulama s├╝resi, giri┼č boyutuyla do─črusal olarak orant─▒l─▒d─▒r.

Ve sadece arama de─čil, i┼č ne olursa olsun (art─▒rma, kar┼č─▒la┼čt─▒rma veya herhangi bir i┼člem) girdi b├╝y├╝kl├╝─č├╝n├╝n bir i┼člevidir.

Bu nedenle, herhangi bir algoritman─▒n O (log n) oldu─čunu s├Âyledi─činizde, y├╝r├╝tme zaman─▒, log n'nin giri┼č b├╝y├╝kl├╝─č├╝d├╝r.

Girdi b├╝y├╝kl├╝─č├╝ artt─▒k├ža yap─▒lan i┼č (burada y├╝r├╝tme s├╝resi) artar.

       n      Work
      2     1 units of work
      4     2 units of work
      8     3 units of work
 

Girdi b├╝y├╝kl├╝─č├╝ artt─▒k├ža yap─▒lan i┼č artar ve makineden ba─č─▒ms─▒zd─▒r. Ve e─čer ├žal─▒┼čma birimlerinin de─čerini bulmaya ├žal─▒┼č─▒rsan─▒z, asl─▒nda yukar─▒da belirtilen parametrelere ba─čl─▒d─▒r. Sistemlere ve hepsine g├Âre de─či┼čecektir.


6








a─ča├ž

log x to base b = y tersi b^y = x

Derinli─či d ve boyut n bir M-ary a─čac─▒n─▒z varsa, o zaman:

  • t├╝m a─čac─▒ gezen ~ O (M ^ d) = O (n)

  • A─ča├žta tek bir yol y├╝r├╝mek ~ O (d) = O (M taban─▒na log n)


5







Bilgi teknolojisinde ┼ču anlama gelir:

   f(n)=O(g(n)) If there is suitable constant C and N0 independent on N, 
  such that
  for all N>N0  "C*g(n) > f(n) > 0" is true.
 

Kar─▒nca bu g├Âsterimde ├žo─čunlukla matematikten al─▒nm─▒┼č gibi g├Âr├╝n├╝yor.

Bu yaz─▒da bir al─▒nt─▒ var: DE Knuth, "B├ťY├ťK OMICRON VE B├ťY├ťK OMEGA VE B├ťY├ťK THETA", 1976 :

Burada tart─▒┼č─▒lan konulara dayanarak, SIGACT ├╝yelerinin ve bilgisayar bilimleri ve matematik dergilerinin edit├Ârlerinin, makul bir ┼čekilde daha k─▒sa s├╝rede daha iyi bir alternatif bulunamad─▒─č─▒ s├╝rece yukar─▒da tan─▒mland─▒─č─▒ gibi g├Âsterimleri kabul etmelerini ├Âneririm .

Bug├╝n 2016, ama bug├╝n hala kullan─▒yoruz.


Matematiksel analizde ┼ču anlama gelir:

   lim (f(n)/g(n))=Constant; where n goes to +infinity
 

Ancak matematiksel analizde bile bazen bu sembol "C * g (n)> f (n)> 0" anlam─▒nda kullan─▒lm─▒┼čt─▒r.

├ťniversiteden bildi─čim kadar─▒yla sembol Alman matematik├ži Landau (1877-1938) taraf─▒ndan uyar─▒ld─▒


5







Asl─▒nda, n ├Â─čelerinin bir listesine sahipseniz ve bu listeden bir ikili a─ča├ž olu┼čturursan─▒z (b├Âlme ve fethetme algoritmas─▒nda oldu─ču gibi), boyut 1'e (yapraklar) eri┼činceye kadar 2'ye b├Âlmeye devam edersiniz.

─░lk ad─▒mda 2'ye b├Âl├╝yorsunuz. Daha sonra 2 listeniz (2 ^ 1) var, her birini 2'ye b├Âl├╝yorsunuz, yani 4 listeniz (2 ^ 2) var, tekrar b├Âl├╝yorsunuz, 8 listeniz var (2 ^ 3 ) ve liste b├╝y├╝kl├╝─č├╝n├╝ze kadar 1

Bu size denklemi verir:

n/(2^steps)=1 <=> n=2^steps <=> lg(n)=steps

(Her bir tarafa ait olan lg'yi al─▒rs─▒n─▒z, lg g├╝nl├╝k taban─▒ 2 olur)


5







Tam ikili ├Ârnek O (ln n) 'dir, ├ž├╝nk├╝ arama ┼č├Âyle g├Âr├╝n├╝r:

 1 2 3 4 5 6 7 8 9 10 11 12
 

4 aran─▒yor 3 isabet var: 6, 3 sonra 4. Ve log2 12 = 3. Gerekti─činde ka├ž isabet ald─▒─č─▒n─▒n iyi bir de─čeri.


3







Sezgiye dayal─▒ bir cevap ar─▒yorsan─▒z, sizin i├žin iki yorum yapmak isterim.

  1. ├çok geni┼č bir tabana sahip ├žok y├╝ksek bir tepe d├╝┼č├╝n├╝n. Tepenin tepesine ula┼čmak i├žin iki yol vard─▒r: biri tepeye kadar sarmal bir ┼čekilde tepeye ula┼čan ├Âzel bir patikad─▒r, di─čeri: bir merdiven sa─člamak i├žin kesilen oymalar gibi k├╝├ž├╝k teraslar. ┼×imdi, ilk yol O (n) do─črusal saatine ula┼č─▒yorsa, ikincisi O (log n) olur.

  2. Bir tamsay─▒y─▒ kabul eden bir algoritma d├╝┼č├╝n├╝n, n girdi olarak ve n o zamana orant─▒l─▒ zamanda tamamlarsa O (n) veya teta (n) olur, ancak o zamana oranla number of digits or the number of bits in the binary representation on number ├žal─▒┼č─▒rsa algoritma O (log n) veya teta'da ├žal─▒┼č─▒r. (log n) zaman.


3







Divide ve Conquer paradigmas─▒ndaki algoritmalar karma┼č─▒kt─▒r O (logn). Burada bir ├Ârnek, kendi g├╝├ž fonksiyonunu hesapla,

 int power(int x, unsigned int y)
{
    int temp;
    if( y == 0)
        return 1;
    temp = power(x, y/2);
    if (y%2 == 0)
        return temp*temp;
    else
        return x*temp*temp;
}
 

dan http://www.geeksforgeeks.org/write-ac-program-to-calculate-powxn/


2



─░lgili yay─▒nlar


C++ 11 standart bir bellek modeli tan─▒tt─▒. Bunun anlam─▒ ne? Ve C++ programlamay─▒ nas─▒l etkileyecek?

C de ÔÇťstatikÔÇŁ ne demektir?

% ~ Dp0 ne anlama geliyor ve nas─▒l ├žal─▒┼č─▒yor?

'Senkronize' ne demektir?

ÔÇťBir aray├╝z├╝ programlamakÔÇŁ ne demektir?

ÔÇťKesme noktas─▒ ┼ču anda ├žarp─▒lmayacak. Kaynak kodu orijinal versiyondan farkl─▒. ÔÇŁBu ne anlama geliyor?

JVM se├žene─či -Xss - Tam olarak ne yapar?

Bu ne anlama geliyor: Serile┼čtirilebilir s─▒n─▒f statik bir final serialVersionUID alan─▒ bildirmiyor mu? [├žift]

MySQL'de ÔÇťTepeg├ÂzÔÇŁ ne demek, bunun k├Ât├╝ yan─▒ nedir ve nas─▒l d├╝zeltilir?

D─▒┼ča aktar─▒lan servis izin gerektirmiyor: bu ne anlama geliyor?

Etiketle ilgili di─čer sorular [time-complexity]


Git'teki en son yerel taahh├╝tleri nas─▒l geri alabilirim?

'Git pull' ve 'git fetch' aras─▒ndaki fark nedir?

Do─čru JSON i├žerik t├╝r├╝ nedir?

Y─▒─č─▒n ve y─▒─č─▒n nerede ve nerede?

Belirli bir ├Â─čeyi JavaScript'teki bir diziden nas─▒l kald─▒r─▒r─▒m?

var functionName = function () {} vs function functionName () {}

Java ÔÇťreferansa g├ÂreÔÇŁ veya ÔÇťde─čere g├ÂreÔÇŁ m─▒?

Bir ├Âzelli─či bir JavaScript nesnesinden nas─▒l kald─▒r─▒r─▒m?

Form tabanl─▒ web sitesi do─črulamas─▒ i├žin kesin k─▒lavuz [kapal─▒]

ActionScript 3'te ÔÇťNullÔÇŁ (ger├žek bir soyad─▒!) Bir SOAP web hizmetine nas─▒l iletilir?