Soru “Big O” gösteriminin sade bir İngilizce açıklaması nedir?


Mümkün olduğunca az biçimsel tanımı ve basit matematiği tercih ederim.


4533
2018-01-28 11:10


Menşei


Özet: Bir algoritmanın karmaşıklığının üst sınırı. Aynı soruya da bakınız Büyük O, nasıl hesaplarsın / tahmin edersin? iyi bir açıklama için. - Kosi2801
Diğer cevaplar oldukça iyidir, bunu anlamak için sadece bir ayrıntı vardır: O (log n) veya benzer araçlar, değerin kendisinin değil, girdinin "uzunluğuna" veya "büyüklüğüne" bağlıdır. Bu anlamak zor olabilir, ama çok önemlidir. Örneğin, algoritmanız her iterasyonda ikişer şeyi böldüğünde gerçekleşir. - Harald Schilly
MIT "Bilgisayar Bilimine Giriş ve Programlama" dersinin 8. dersinde algoritmaların karmaşıklığına adanmış bir ders var. youtube.com/watch?v=ewd7Lf2dr5Q Tamamen sade bir İngilizce değildir, ancak kolayca anlaşılabilir olan örneklerle güzel bir açıklama sunar. - ivanjovanovic
Big O, algoritmanın maksimum tekrar sayısını gerçekleştireceği varsayılarak bir işlevin en kötü durum performansının bir tahminidir. - Paul Sweatte
Big-O notation explained by a self-taught programmer - Soner Gönül


Cevaplar:


Hızlı not, bu neredeyse kesinlikle kafa karıştırıcı Büyük o notasyonu (ki bu bir üst sınırdır) Theta gösterimi ile (iki taraflı bir bağdır). Deneyimlerimde bu, akademik olmayan ortamlardaki tartışmaların tipik bir örneğidir. Herhangi bir karışıklık için özür dilerim.


Büyük O karmaşıklığı bu grafikle görselleştirilebilir:

Big O Analysis

Big-O notasyonu için verebileceğim en basit tanım şudur:

Big-O notasyonu, bir algoritmanın karmaşıklığının göreli bir temsilidir.

Bu cümlede önemli ve kasten seçilmiş kelimeler var:

  • bağıl: Elmaları sadece elmalarla kıyaslayabilirsiniz. Tamsayıların listesini sıralayan bir algoritmaya aritmetik çarpma yapmak için bir algoritmayı karşılaştıramazsınız. Fakat aritmetik işlemler yapmak için iki algoritmanın bir karşılaştırması (bir çarpma, bir ekleme) size anlamlı bir şey söyleyecektir;
  • gösterimi: 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 göre karşılaştırılır (göreli sıralamayı belirlemek için iki düğüm karşılaştırılır). Bu, karşılaştırmanın pahalı olduğunu varsayar. Ama eğer karşılaştırma ucuzsa ve takas pahalıysa? Karşılaştırmayı değiştirir; ve
  • karmaşıklığı: 10.000 öğeyi sıralamak bana bir saniye sürerse, bir milyonu sıralamak ne kadar sürer? Bu örnekte karmaşıklık, başka bir şeye göreceli bir ölçüdür.

Geri kalanını okuduktan sonra geri gel ve oku.

Düşünebildiğim Big-O'nun en iyi örneği aritmetik yapmaktır. İki sayı al (123456 ve 789012). Okulda öğrendiğimiz temel aritmetik işlemler:

  • ilave;
  • çıkarma;
  • çarpma işlemi; ve
  • bölünme.

Bunların her biri bir işlem veya bir problemdir. Bunları çözmek için bir yöntem denir algoritma.

Ekleme en basit olanıdır. Sayıları sıraya (sağa) sıralarsınız ve haneleri, sonuçta o ekleme işleminin son sayısını yazan bir sütuna eklersiniz. Bu sayının 'onlarca' bölümü bir sonraki sütuna taşınır.

Bu sayıların eklenmesinin, bu algoritmada en pahalı işlem olduğunu varsayalım. Bu iki sayıyı bir araya getirmek için 6 rakamı bir araya getirmemiz (ve muhtemelen 7'nci taşıyabilmek) gerekçesiyle duruyor. İki 100 basamaklı sayı eklediğimizde 100 ek yapmamız gerekiyor. Eklersek iki 10.000 haneli rakamlar 10.000 eklemeler yapmalıyız.

Deseni görüyor musun? karmaşa (işlem sayısı), rakamların sayısıyla doğru orantılıdır n daha büyük sayıda. Buna deriz O (n) veya doğrusal karmaşıklık.

Çıkarma benzerdir (taşıma yerine ödünç almanız gerekebilir).

Çarpma farklıdır. Numaraları sıraya diziyorsunuz, ilk rakamı alt sayıya alıyorsunuz ve her rakamın üstündeki her sayıya karşılık olarak her hane için çarpın. Yani iki 6 basamaklı numaramızı çoğaltmak için 36 çarpma yapmalıyız. Son sonucu elde etmek için 10 veya 11 sütun eklemeye ihtiyacımız olabilir.

İki 100 basamaklı numaramız varsa, 10.000 çarpma ve 200 ek yapmamız gerekir. İki milyon haneli rakam için bir trilyon yapmamız gerekiyor (1012) çoğaltmalar ve iki milyon ekler.

Algoritma n ile ölçeklendirilirkaresi, bu O (n2) veya karesel karmaşıklık. Bu başka önemli bir kavram tanıtmak için iyi bir zaman:

Sadece karmaşıklığın en önemli kısmını önemsiyoruz.

Astute, işlem sayısını şu şekilde ifade edebileceğimizi fark etmiş olabilir: n2 + 2n. Fakat bizim örneğimizde gördüğünüz gibi, iki rakamı bir milyon rakamı olan bir parçayla, ikinci dönem (2n) önemsiz hale gelir (bu aşamadaki toplam işlemlerin% 0.0002'sini oluşturur).

Burada en kötü senaryoyu üstlendiğimizi fark edebiliyoruz. Biri 4 haneli, diğeri 6 haneli ise 6 basamaklı sayıları çarparken, sadece 24 çarpma var. Yine de, 'n' için en kötü durum senaryosunu hesaplıyoruz, yani her ikisi de 6 haneli rakamlar. Bu nedenle Big-O notasyonu, bir algoritmanın en kötü durum senaryosu hakkındadır.

Telefon rehberi

Düşünebildiğim en iyi örnek, normalde Beyaz Sayfalar veya benzerleri olarak adlandırılan telefon defteridir, ancak ülkeden ülkeye farklılık gösterir. Ama ben insanlar soyadı ve sonra baş harfleri veya ad, muhtemelen adres ve sonra telefon numaralarını listeleyen biri hakkında konuşuyorum.

Şimdi bir bilgisayardan 1000.000 isim içeren bir telefon rehberinde "John Smith" telefon numarasını aramak için talimat veriyor olsaydınız ne yapardınız? S'nin ne kadar uzandığını tahmin edebileceğiniz gerçeğini göz ardı ederek (yapamayacağınızı varsayalım), ne yapardınız?

Tipik bir uygulama ortada açmak olabilir, 500.000inci ve "Smith" ile karşılaştır. Eğer "Smith, John" olsaydı, gerçekten şanslıyız. Daha büyük olasılıkla, "John Smith" in bu ismin öncesinde veya sonrasında olması. Eğer öyleyse, telefon rehberinin son yarısını ikiye böler ve tekrar ederiz. Önceden ise telefon rehberinin ilk yarısını ikiye bölüyoruz ve tekrarlıyoruz. Ve bunun gibi.

Bu bir denir Ikili arama ve bunu fark edip etmediğinizi programlayarak her gün kullanılır.

Yani, milyonlarca ismin bir telefon rehberinde bir isim bulmak istiyorsanız, bunu en fazla 20 kez yaparak herhangi bir ismi bulabilirsiniz. Arama algoritmalarını karşılaştırırken, bu karşılaştırmanın bizim 'n' olduğuna karar verdik.

  • 3 ismin bir telefon rehberi için 2 karşılaştırma (en fazla) alır.
  • 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?

Big-O terimlerinde bu O (log n) veya logaritmik karmaşıklık. Şimdi söz konusu logaritma ln (baz e), kütük olabilir10, günlük2 veya başka bir baz. O'nun O (2 nolu) gibi O'nun (log n) önemi yok.2) ve O (100n2) hala ikisi de (n)2).

Bu noktada, Big O'nun bir algoritma ile üç vakayı belirlemek için kullanılabileceğini açıklamak yararlıdır:

  • En iyi senaryo: Telefon rehberi araştırmasında, en iyi durum, adı bir karşılaştırma olarak bulmamızdır. Bu O (1) veya sürekli karmaşıklık;
  • Beklenen Durum Yukarıda tartışıldığı gibi bu, O'dur (log n); ve
  • En kötü durumda: Bu da O (log n).

Normalde en iyi durumu umursamıyoruz. Beklenen ve en kötü durumla ilgileniyoruz. Bazen bunlardan biri veya diğeri daha önemli olacaktır.

Telefon defterine dönün.

Bir telefon numaranız varsa ve bir isim bulmak istiyorsanız ne olur? Polisin bir ters telefon kitabı var, ancak bu tür bakışlar genel halka reddediliyor. Yoksa öyle mi? Teknik olarak sıradan bir telefon rehberinde bir numarayı arayabilirsin. Nasıl?

İlk addan başlayıp numarayı karşılaştırırsınız. Eğer bir eşleşme ise, harika, eğer değilse, bir sonraki aşamaya geçersiniz. Bunu böyle yapmalısın çünkü telefon defteri sırasız (yine de telefon numarasıyla).

Telefon numarası verilen bir isim bulmak için (geriye doğru arama):

  • En iyi senaryo: O (1);
  • Beklenen Durum O (n) (500,000 için); ve
  • En kötü durumda: O (n) (1.000.000 için).

Gezgin Satıcı

Bu bilgisayar bilimlerinde oldukça ünlü bir sorundur ve bir sözü hak ediyor. Bu problemde N Kasabası var. Bu şehirlerin her biri, belirli bir mesafe olan bir yolla 1 veya daha fazla başka şehre bağlanır. Gezgin Satış Görevlisi problemi, her şehri ziyaret eden en kısa turu bulmaktır.

Kulağa basit geliyor? Tekrar düşün.

Tüm çiftler arasındaki yollarda A, B ve C kasabalarınız varsa, şunları yapabilirsiniz:

  • A → B → C
  • A → C → B
  • B → C → A
  • B → A → C
  • C → A → B
  • C → B → A

Aslında bundan daha azı vardır, çünkü bunlardan bazıları eşdeğerdir (A → B → C ve C → B → A eşdeğerdir, çünkü aynı yolları kullanırlar, tersine).

Gerçekte 3 olasılık vardır.

  • Bunu 4 kasabaya götür ve (iirc) 12 ihtimalin var.
  • 5 ile 60.
  • 6 360 olur.

Bu, adında bir matematiksel işlemin bir işlevidir. faktöryel. 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 × 1064

Bu yüzden, Salesman Satıcı probleminin Big-O'su O (n!) veya Faktöriyel veya kombinatoryal karmaşıklık.

200 kasabaya geldiğinizde, geleneksel bilgisayarlarla sorunu çözmek için evrende yeterli zaman kalmadı.

Düşünmek için bir şey.

Polinom Zaman

Hızlı bir şekilde bahsetmek istediğim bir başka nokta da karmaşıklığı olan herhangi bir algoritmanın olmasıdır. O (nbir) sahip olduğu söyleniyor polinom karmaşıklığı veya içinde çözülebilir polinom zamanı.

O (n), O (n)2) vb tüm polinom zaman vardır. Bazı problemler polinom zamanında çözülemez. Bunun için dünyada bazı şeyler kullanılıyor. Genel Anahtar Şifreleme, en iyi örneklerden biridir. Çok büyük sayıdaki iki ana faktörün bulunması zor bir hesaplamadır. Değilse, kullandığımız ortak anahtar sistemlerini kullanamadık.

Her neyse, bu benim için (Umarım sade İngilizce) Big O'nun (revize edilmiş) açıklaması içindir.


6094
2018-01-28 11:18



Diğer cevaplar O (1), O (n ^ 2) ve diğerleri arasındaki farkları açıklamaya odaklanırken, sizler algoritmaların n ^ 2, nlog (n) vb. 1 Büyük O notasyonunu anlamama yardımcı olan iyi bir cevap için - Yew Long
Bu büyük-O'nun bir üst sınırı (bir algoritma tarafından verilen) temsil ettiğini eklemek isteyebilir, büyük Omega alt sınırı (genellikle belirli bir algoritmadan bağımsız olarak kanıt olarak verilir) verir ve büyük-Theta, "optimal" algoritma anlamına gelir. bu alt sınıra ulaşmak bilinir. - mdm
En uzun cevabı arıyorsanız, ancak bu, Big-O’yu basit bir şekilde en iyi açıklayan cevap için iyi olmaz. - kirk.burleson
-1: Bu açıkça yanlıştır: _ "BigOh, algoritmanın karmaşıklığının göreli temsilidir". Hayır. BigOh, bir asimptotik üst sınırdır ve bilgisayar bilimlerinden oldukça bağımsızdır. O (n) doğrusaldır. Hayır, BigOh'u teta ile karıştırıyorsun. log n, O (n) dir. 1, O (n) 'dir. TheO'nun BigOh ile karıştırılmasının temel hatasını yapan bu yanıtın (ve yorumların) upvotlarının sayısı oldukça ...
"200 kasabaya geldiğinizde, geleneksel bilgisayarlarla sorunu çözmek için evrende yeterli zaman kalmıyor." Evren sona erecek mi? - Isaac


Bir algoritmanın nasıl ölçeklendiğini gösterir.

O (n2): olarak bilinir Kuadratik karmaşıklık

  • 1 ürün: 1 saniye
  • 10 öğe: 100 saniye
  • 100 ürün: 10000 saniye

Öğelerin sayısının 10 kat arttığına dikkat edin, ancak süre 10 kat artar.2. Temel olarak, n = 10 ve böylece O (n2) bize ölçekleme faktörü n verir2 hangisi 102.

O (n): olarak bilinir Doğrusal karmaşıklık

  • 1 ürün: 1 saniye
  • 10 öğe: 10 saniye
  • 100 öğe: 100 saniye

Bu sefer öğe sayısı 10 kat artar, ve zaman da öyle. n = 10 ve benzeri O (n) 'nin ölçekleme faktörü 10'dur.

O (1): olarak bilinir Sabit karmaşıklık

  • 1 ürün: 1 saniye
  • 10 öğe: 1 saniye
  • 100 ürün: 1 saniye

Eşya sayısı hala 10 kat artmaktadır, ancak O (1) 'in ölçeklendirme faktörü her zaman 1'dir.

O (log n): olarak bilinir Logaritmik karmaşıklık

  • 1 ürün: 1 saniye
  • 10 öğe: 2 saniye
  • 100 ürün: 3 saniye
  • 1000 ürün: 4 saniye
  • 10000 ürün: 5 saniye

Hesaplama sayısı sadece giriş değerinin bir kaydı ile artırılır. Bu durumda, her bir hesaplamanın 1 saniye sürdüğü varsayıldığında, girişin günlüğü n gerekli zaman, dolayısıyla log n.

Bu onun özü. Matematiği indiriyorlar, bu yüzden tam olarak n olmayabilir.2 ya da söyledikleri her neyse, ama ölçeklemede baskın faktör olacak.


662
2018-01-28 11:28



Bu tanım tam olarak ne anlama geliyor? (Eşya sayısı hala 10 kat artar, ancak O (1) ölçeklendirme faktörü her zaman 1'dir.) - HollerTrain
Saniye değil, operasyonlar. Ayrıca, faktöriyel ve logaritmik zamanı da kaçırdınız. - Chris Charabaruk
Bu, O (n ^ 2) 'nin tam olarak çalışan bir algoritmayı tanımlayabileceğini çok iyi açıklamıyor .01 * n ^ 2 + 999999 * n + 999999. Algoritmaların bu ölçek kullanılarak karşılaştırıldığını bilmek önemlidir. Karşılaştırma, n "yeterince büyük" olduğunda çalışır. Python'un zaman dilimi aslında küçük bir ek yüke sahip olması nedeniyle küçük diziler için ekleme sıralama (en kötü / ortalama durum O (n ^ 2)) kullanır. - Darthfett
Bu cevap ayrıca büyük O notasyonu ve Theta gösterimini karıştırır. Tüm girdiler için 1 döndüren n'nin işlevi (genellikle basitçe 1 olarak yazılır) aslında O (n ^ 2) 'de (O (1) de olsa bile). Benzer şekilde, sabit bir zaman alan sadece bir adım yapmak zorunda olan bir algoritmanın da bir O (1) algoritması olduğu, aynı zamanda bir O (n) ve bir O (n ^ 2) algoritması olduğu düşünülmektedir. Ama belki matematikçiler ve bilgisayar bilimcileri bu tanımı kabul etmiyorlar: - /. - Jacob Akkerboom
O (log n) Bu cevapta düşünülen logaritmik karmaşıklık, temel 10'dur. Genel olarak, standart, 2 tabanı ile hesaplanır. Birisi bu gerçeği akılda tutmalı ve kafam karışmamalı. Ayrıca @ChrisCharabaruk tarafından belirtildiği gibi karmaşıklık, işlem sayısını ve saniyeler değil. - Aksh1801


Big-O notasyonu ("asimptotik büyüme" olarak da adlandırılır) orijine yakın sabit faktörleri ve maddeleri görmezden geldiğinizde "nasıl görünür". Bunu konuşmak için kullanıyoruz nasıl bir şey.


temeller

"Yeterli" büyük girdiler için ...

  • f(x) ∈ O(upperbound) anlamına geliyor f "daha hızlı büyür" upperbound
  • f(x) ∈ Ɵ(justlikethis) anlamına gelmek f "tam olarak büyür" justlikethis
  • f(x) ∈ Ω(lowerbound) anlamına geliyor f "daha yavaş büyür" lowerbound

big-O notasyonu sabit faktörleri umursamıyor: fonksiyon 9x² "tam olarak büyür" denir 10x². Büyük-O da değil asimptotik gösterim hakkında olmayan asimptotik şeyler ("orijine yakın şeyler" veya "sorun boyutu küçük olduğunda ne olur"): işlev 10x² "tam olarak büyür" denir 10x² - x + 2.

Neden denklemin daha küçük kısımlarını görmezden gelmek istersiniz? Çünkü daha büyük ve daha büyük ölçekleri düşündüğünüzde denklemin büyük parçaları tarafından tamamen cüceleştirilirler; Onların katkısı cüce ve alakasız hale gelir. (Örnek bölümüne bakınız.)

Başka bir deyişle, her şeyle ilgili. oran sonsuzluğa gittiğinizde. Gerçek zamanını bölerseniz, O(...)Büyük girdilerin sınırında sabit bir faktör elde edersiniz. Sezgisel olarak bu mantıklıdır: diğerini elde etmek için birisini çarpabilirseniz, işlevler "birbirini" gibi ölçeklendirir. Yani, derken ...

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

... bu şu demek "yeterince büyük" sorun boyutları N için (eğer orijinin yakınında olan şeyleri görmezden gelirsek), şöyle ki, bazı sabitler (ör. 2.5, tamamen oluşur) vardır:

actualAlgorithmTime(N)                 e.g. "mergesort_duration(N)       "
────────────────────── < constant            ───────────────────── < 2.5 
       bound(N)                                    N log(N)         

Pek çok sabit 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 geldiğimiz gibi görmezden geliriz (genellikle neden önemli olmadığı için Sabit Faktörler bölümüne bakınız). Yukarıdaki denklemi bir sınır olarak da düşünebilirsiniz.En kötü senaryoda, bu süre, kabaca daha kötü olamaz. N*log(N), 2.5 katsayısı (çok fazla önemsemediğimiz sabit bir faktör)".

Genel olarak, O(...) En kullanışlı olanıdır çünkü en kötü durum davranışlarını önemseriz. Eğer f(x) işlemci veya bellek kullanımı gibi "kötü" bir şeyi temsil eder, sonra "f(x) ∈ O(upperbound)" anlamına geliyor "upperbound işlemci / bellek kullanımının en kötü durum senaryosudur ".


Uygulamalar

Tamamen matematiksel bir yapı olarak, big-O notasyonu işlem süresi ve hafıza hakkında konuşmakla sınırlı değildir. Ölçeklemenin anlamlı olduğu her şeyin asimptotiklerini tartışmak için bunu kullanabilirsiniz:

  • arasında muhtemel tokalaşma sayısı N bir partide insanlar (Ɵ(N²)özellikle N(N-1)/2ama önemli olan, "olduğu gibi" )
  • zamanın bir fonksiyonu olarak bazı viral pazarlamayı gören kişilerin olasılıklı beklenen sayısı
  • Web sitesi gecikmesi, CPU veya GPU veya bilgisayar kümesindeki işlem birimi sayısı ile ölçeklendirilir
  • CPU üzerindeki ısı çıkışı ölçeklerinin transistör sayısı, voltajı vb.
  • Giriş boyutunun bir fonksiyonu olarak bir algoritmanın ne kadar süre çalışması gerektiği
  • Giriş boyutunun bir fonksiyonu olarak, bir algoritmanın ne kadar alan çalıştırması gerektiği

Örnek

Yukarıdaki el sıkışma örneği için, bir odadaki herkes herkesin elini sıkıyor. Bu örnekte, #handshakes ∈ Ɵ(N²). Niye ya?

Biraz yedekle: el sıkışma sayısı tam olarak n-choose-2 veya N*(N-1)/2 (N halkının her biri, diğer insanların N-1'inin ellerini sallar, ancak bu iki kez el sıkışmalarını 2'ye böler):

everyone handshakes everyone else. Image credit and license per wikipedia/wikimedia commons "complete graph" article.  adjacency matrix

Ancak, çok sayıda insan için, doğrusal terim N dwarfededir ve etkin bir şekilde orantılı olarak 0'a katkıda bulunur (grafikte: toplam kutuların üzerindeki diyagonaldeki boş kutuların oranı, katılımcıların sayısı arttıkça küçülür). Bu nedenle ölçekleme davranışı order N²ya da el sıkışmalarının sayısı "N² gibi büyür".

#handshakes(N)
────────────── ≈ 1/2
     N²

Grafiğin diyagonalindeki boş kutular (N * (N-1) / 2 onay işareti) bile yokmuş gibi (N)2 onay işaretlerini asimptotik olarak).

(sade İngilizce'den geçici bir şekilde baskı) :) Eğer bunu kendinize kanıtlamak isterseniz, o kadar çok terime bölmek için oran üzerinde basit bir cebir yapabilirdiniz (lim"Sınırda kabul edilir" anlamına gelir, sadece görmediyseniz göz ardı edin, sadece "ve N gerçekten büyük" ifadesidir.

    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ı 'x²' ye büyük değerler için çok benziyor, eğer # handshake / x² oranını yazarsak, ihtiyacımız olmaması gerçeği. kesinlikle x² tokalaşma, keyfi olarak büyük bir süre için ondalıklıkta bile ortaya çıkmazdı.

Örneğin. x = 1million, oran # handshakes / x²: 0.499999 ...


Bina Sezgisi

Bu bizim gibi ifadeler yapalım ...

"Yeterince büyük inputsize = N için, sabit faktör ne olursa olsun, eğer çift giriş boyutu


362
2017-07-08 04:46



Mükemmel bir matematiksel cevap, ancak OP sade bir İngilizce cevap istedi. Bu matematiksel tanımlama düzeyi, cevabı anlamak için gerekli değildir, ancak özellikle matematiksel olarak düşünen insanlar için “sade İngilizce” den daha anlaşılması daha kolay olabilir. Ancak OP, ikincisini istedi. - El Zorko
Muhtemelen OP dışındaki kişiler bu sorunun cevabına ilgi duyabilir. Bu sitenin yol gösterici ilkesi değil mi? - Casey
İnsanların neden benim cevabımı kaybolabileceğini ve çok fazla mathy (özellikle de "matematik, yeni düz ingilizce" ifadesidir, çünkü kaldırıldığından beri) yorumlayabiliyorken, asıl soru büyük-O'nun işlevlerle ilgili olduğunu sorar. Açık-İngilizce ve sezgisel-İngilizce sezgisini tamamlayacak şekilde işlevler hakkında konuşmaya çalışın. Buradaki matematik genellikle üstesinden gelinebilir ya da bir yüksekokul matematik arka planı ile anlaşılabilir. İnsanların sonunda Math Addenda'ya bakabileceğini hissediyorum, ve cevabın bir parçası olduğunu varsayalım, sadece ne olduğunu görmek için gerçek matematik gibi görünüyor. - ninjagecko
Bu harika bir cevaptır; En çok oyu olandan çok daha iyi IMO. Gerekli olan "matematik", "O" dan sonra parantez içindeki ifadeleri anlamak için gerekenleri aşmaz; - Dave Abrahams
"f (x) ∈ O" (üstte), "bu üç basit ifadeden daha hızlı" değil, "büyük" anlamına gelir, ancak büyük Oh, Theta ve Omega'nun matematiksel olarak uygun açıklamaları altındır. Düz İngilizce dilinde bana, 5 farklı kaynağın karmaşık matematiksel ifadeler yazmadan bana tercüme edilemeyeceği noktasında anlattı. Teşekkürler dostum! :) - timbram


DÜZENLEME: Hızlı not, bu neredeyse kesinlikle kafa karıştırıcı Büyük o notasyonu (bir üst sınırdır) Theta gösterimi ile (hem üst hem de alt sınır olan). Deneyimlerimde bu, akademik olmayan ortamlardaki tartışmaların tipik bir örneğidir. Herhangi bir karışıklık için özür dilerim.

Bir cümlede: İşinizin boyutu arttıkça, bunu tamamlamak ne kadar sürer?

Açıkçası, bu sadece girdi olarak "boyut" ve çıktı olarak "süre" olarak kullanılır - bellek kullanımı hakkında konuşmak istediğinizde aynı fikir geçerlidir.

İşte kurutmak istediğimiz N Tişörtlerimizin bulunduğu bir örnek. İyi üstlenmek Bunları kurutma pozisyonunda elde etmek inanılmaz derecede hızlıdır (yani insan etkileşimi göz ardı edilebilir). Bu gerçek hayatta durum böyle değil elbette ...

  • Dışarıda bir yıkama çizgisi kullanmak: sonsuz büyük bir arka bahçeye sahip olduğunuzu varsayarak, yıkama O (1) zamanda kurur. Bununla birlikte çok fazla var, aynı güneşi ve temiz havayı alacak, böylece boyut kuruma süresini etkilemeyecek.

  • Bir çamaşır kurutma makinası kullanarak: Her yüke 10 gömlek koyarsınız ve bir saat sonra yapılır. (Buradaki gerçek sayıları dikkate almayın - alakasızlar.) Yani 50 gömlek kurutma hakkında 10 gömlek kurutma kadar 5 kez.

  • Her şeyi bir hava dolabına koymak: Eğer her şeyi büyük bir küme içine koyarsak ve genel ısının bunu yapmasına izin verirsek, orta gömleklerin kuruması uzun zaman alacaktır. Ayrıntıyı tahmin etmek istemem ama en azından O (N ^ 2) olduğundan şüpheleniyorum - yıkama yükünü arttırdıkça, kurutma süresi daha hızlı artıyor.

"Büyük O" gösteriminin önemli bir yönü de değil Belirli bir boyut için hangi algoritmanın daha hızlı olacağını söyleyiniz. Bir hashtable (dize anahtarı, tamsayı değeri) ve bir çiftler dizisi (dize, tamsayı) alın. Dizideki hashtable veya bir elementte bir anahtar bulmak daha mı hızlıdır? (yani dizi için, "string parçasının verilen anahtarla eşleştiği ilk elemanı bulun.") Hashtables genellikle amortismana tabi tutulur (~ = "ortalama") O (1) - bir kez kurulduktan sonra 1.000 giriş tablosunda olduğu gibi 100 giriş tablosunda bir giriş bulmak için aynı zamanda. Bir dizide (dizinden ziyade içeriğe göre) bir elementin bulunması doğrusaldır, yani O (N) - ortalama olarak, girişlerin yarısına bakmak zorunda kalacaksınız.

Bu, arama için bir diziden daha hızlı bir karma hale getirir mi? Şart değil. Çok küçük bir girişler koleksiyonunuz varsa, bir dizi daha hızlı olabilir - baktığınız zamanın kod numarasını hesaplamak için gereken süre içinde tüm dizeleri kontrol edebilirsiniz. Bununla birlikte, veri seti büyüdükçe, hashtabı sonunda diziyi yenecektir.


237
2018-01-28 11:16



Bir hashtable, gerçek dizinin indeksini hesaplamak için bir algoritma gerektirir (uygulamaya bağlı olarak). Ve bir dizi sadece O (1) var çünkü bu sadece bir adres. Ama bu sorunun bir ilgisi yok, sadece bir gözlem :) - Filip Ekberg
jon’un açıklaması, düşündüğüm soruyla çok fazla ilgili. tam olarak bunu bir anneye nasıl açıklayabildiğini ve nihayetinde anlayacağını düşündüğümü anladım :) kıyafet örneğini beğendim (özellikle sonuncusu, karmaşıklığın katlanarak büyümesini açıklıyor) - Johannes Schaub - litb
Filip: Dizine göre bir dizi adresi hakkında konuşmuyorum, dizide eşleşen bir giriş bulmaya çalışıyorum. Cevabı tekrar okuyabilir ve hala belirsiz olup olmadığını görebilir misiniz? - Jon Skeet
@Filip Ekberg Sanırım her dizinin bir anahtarla doğrudan ilişkilendirildiği bir doğrudan-adres tablosu düşünürsünüz. O zaman (1), Jon'un aramanız gereken bir dizi anahtar / değer çifti hakkında konuştuğunu düşünüyorum. doğrusal olarak. - ljs
@RBT: Hayır, ikili bir bakış değil. Doğru hash elde edebilir Kova hemen, sadece karma koddan kova dizinine dönüşüme dayalı. Bundan sonra, kovadaki doğru karma kodu bulmak doğrusal olabilir veya ikili bir arama olabilir ... ancak o zamana kadar, kelimenin toplam büyüklüğünün çok küçük bir oranına inersiniz. - Jon Skeet


Büyük O, bir fonksiyonun büyüme davranışı üzerindeki bir üst limiti, örneğin bir programın çalışma zamanını, girdi büyük olduğunda tanımlar.

Örnekler:

  • O (n): Giriş boyutunu iki katına çıkarırsam çalışma zamanı iki katına çıkar

  • O (n2): Giriş boyutu çalışma zamanı dört katına çıkarsa

  • O (log n): Giriş boyutu iki katına çıkarsa, çalışma zamanı bir artar

  • O (2n): Giriş boyutu bir artarsa, çalışma zamanı iki katına çıkar

Giriş boyutu genellikle girişi temsil etmek için gerekli bitlerdir.


120
2018-01-28 11:23



yanlış! örneğin O (n): Giriş boyutunu iki katına çıkarırsam, çalışma zamanı sonlu sıfır olmayan sabit ile çarpacaktır. Demek istediğim O (n) = O (n + n) - arena-ru
F (n) = O (g (n)) deki f'den bahsediyorum, anladığınız gibi g değil. - starblue
Ayrıldım, ama son cümle bana çok fazla katkıda bulunmuyor. Büyük (O) 'yı tartışırken veya ölçerken sıklıkla "bitler" den bahsetmiyoruz. - cdiggins
O (n log n) için bir örnek eklemelisiniz. - Christoffer Hammarström
Bu çok açık değil, aslında O (n) 'den biraz daha kötü davranıyor. Yani n iki katına çıkarsa, çalışma zamanı 2'den biraz daha büyük bir faktörle çarpılır. - starblue


Büyük O notasyonu, programlayıcılar tarafından genellikle, bir girdi (algoritmanın) giriş setinin büyüklüğünün bir fonksiyonu olarak ifade edilen tamamlanma süresinin 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 kesin Büyük o notasyonu Bir fonksiyonun asimptotik davranışını ifade etmek için kullanılır. Bu, fonksiyonun sonsuza yaklaştıkça nasıl davrandığını gösterir.

Çoğu durumda, bir algoritmanın "O", aşağıdaki durumlardan birine girer:

  • O (1) - Tamamlanma süresi, giriş setinin büyüklüğünden bağımsız olarak aynıdır. Bir örnek dizine göre bir dizi elemanına erişiyor.
  • O (Log N) - Tamamlanma süresi, log2 (n) ile paralel olarak artar. Örneğin, 1024 ürün, 32 öğenin yaklaşık iki katı uzunluğundadır, çünkü Log2 (1024) = 10 ve Log2 (32) = 5'dir. ikili arama ağacı (TSİ).
  • O (N) - Bu giriş setinin büyüklüğü ile doğrusal olarak ölçeklendirme zamanı. Diğer bir deyişle, giriş kümesindeki öğelerin sayısını iki katına çıkarırsanız, algoritma yaklaşık iki kat daha uzun sürer. Bir örnek, bağlantılı bir listedeki öğe sayısını sayar.
  • O (N Log N) - Tamamlama süreleri, öğelerin sayısına göre art arda Log2 (N) sonucunu verir. Bunun bir örneği yığın sıralaması ve hızlı sıralama.
  • O (N ^ 2) - Tamamlanma süresi, kabaca parça sayısının karesine eşittir. Bunun bir örneği kabarcık sıralaması.
  • O (N!) - Tamamlanma süresi, giriş setinin faktörleridir. Bunun bir örneği seyahat eden satıcı problemi kaba kuvvet çözümü.

Büyük O, girdi boyutunun sonsuzluğa doğru artması nedeniyle bir fonksiyonun büyüme eğrisine anlamlı bir şekilde katkıda bulunmayan faktörleri göz ardı eder. Bu, işlev tarafından eklenen veya çarpılan sabitlerin basitçe yok sayıldığı anlamına gelir.


97
2017-09-05 16:31



cdiggins, eğer O (N / 2) karmaşıklığım varsa, O (N) veya O (N / 2) olmalıdır, örneğin, eğer ikincisinin yarısı ikincisine geçecek olursam karmaşıklık. - Melad Ezzat
@Melad Bu, işleve çarpan bir sabit (0.5) örneğidir. Bu, N'nin çok büyük değerleri için anlamlı bir etkiye sahip olduğu düşünüldüğü için göz ardı edilir. - cdiggins


Büyük O, "kodumu çalıştırmak için ne kadar zaman / alan alır?" Şeklinde kendinizi ortak bir şekilde "ifade etmenin" bir yoludur.

Sıklıkla O (n), O (n) yi görebilirsiniz.2), O (nlogn) ve benzerleri, bunların hepsi göstermek için sadece yollar; Bir algoritma nasıl değişir?

O (n) Büyük O'nun n olduğunu ve şimdi "n nedir?" Diye düşünebilirsiniz. Peki "n" elementlerin miktarıdır. Bir Dizide bir Öğe aramak istediğiniz görüntüleme. Her öğeye ve "Doğru eleman / öğe misiniz?" en kötü durumda, madde son endekste, yani listedeki maddeler kadar çok zaman harcadığı anlamına gelir, bu yüzden jenerik olmak için "oh hey, n adil bir değer verilen miktardır!" .

Öyleyse neyi anlayabiliyorsun?2"demek, ancak daha spesifik olmak için, basit bir düşüncenizle, sıralama algoritmalarının basitleştiricisi ile oynayın, baloncuklar. Bu algoritmanın, her öğe için tüm listeye bakması gerekir.

Listem

  1. 1
  2. 6
  3. 3

Buradaki akış şöyle olurdu:

  • En büyük olan 1 ve 6'yı karşılaştırın. OK 6 doğru pozisyonda ilerliyor!
  • 6 ve 3'ü karşılaştırın, oh, 3 daha az! Hadi onu değiştirelim, liste değişti, şimdi baştan başlamalıyız!

Bu O n2 çünkü listedeki tüm öğelere bakmanız gerekiyor "n" öğeleri. Her bir öğe için, karşılaştırmak için tüm öğelere bir kez daha bakarsınız, bu da "n" dir, bu yüzden her öğe için "n" zaman anlamında n * n = n anlamına gelir.2

Umarım istediğin kadar basittir.

Ama unutma, Büyük O sadece zaman ve mekan biçiminde kendini açığa çıkarmanın bir yoludur.


77
2018-01-28 11:14



logN için 0'dan N / 2'ye kadar olan döngü için düşünelim. O (log log N)? Program nasıl gözüküyor? saf matematik becerileri için beni affet - Pablo Escobar


Büyük O, bir algoritmanın temel ölçekleme yapısını tanımlar.

Big O'nun belirli bir algoritma hakkında size söylemediği pek çok bilgi var. Kemiğe yapışır ve sadece algoritmanın ölçekleme doğası hakkında bilgi verir, özellikle de bir algoritmanın "girdi büyüklüğüne" yanıt olarak kullandığı kaynakların (düşünme zamanı veya bellek) kullanımı.

Bir buhar motoru ve bir roket arasındaki farkı göz önünde bulundurun. Onlar sadece aynı şeyin farklı çeşitleri değiller (örneğin, bir Prius motoru ile bir Lamborghini motoru gibi), ancak çekirdeğindeki farklı türde itiş sistemleridir. Bir buhar motoru, bir oyuncak roketinden daha hızlı olabilir, ancak hiçbir buhar pistonu motoru, bir yörüngesel fırlatma aracının hızlarına erişemeyecektir. Bunun nedeni, bu sistemlerin belirli bir hıza ("giriş büyüklüğü") ulaşmak için gereken yakıtın ("kaynak kullanımı") ilişkisine göre farklı ölçeklendirme özelliklerine sahip olmasıdır.

Bu neden bu kadar önemli? Çünkü yazılım, trilyona kadar olan faktörlere göre farklılıklar gösterebilen problemlerle uğraşır. Bunu bir an için düşünün. Ay'a seyahat etmek için gereken hız ve insanın yürüme hızı arasındaki oran 10,000: 1'den azdır ve bu, giriş boyutundaki yazılımların karşılaşabileceği yüzeye kıyasla kesinlikle küçüktür. Ve yazılım giriş boyutlarında astronomik bir aralıkla karşılaşabileceğinden, herhangi bir uygulama detayını koyacak bir algoritmanın Büyük O karmaşıklığı, temel ölçeklendirme doğası için potansiyel vardır.

Kanonik sıralama örneğini ele alalım. Kabarcık sıralaması O (n)2) Birleştirme sıralama O (n log n) iken. Diyelim ki, iki sıralama uygulamanız olduğunu ve A tipi sıralama kullanan kabarcık-sıralama ve uygulama B'yi kullanan A uygulamasına sahip olduğunuzu varsayalım ki, yaklaşık 30 elemanın giriş boyutları için uygulama A'nın sıralamada B uygulamasından 1000 kat daha hızlı olduğunu söyleyelim. 30'dan fazla elementi ayırmak zorunda kalmazsanız, bu giriş boyutlarında çok daha hızlı olduğu için, A uygulamasını tercih etmeniz gerektiği açıktır. Bununla birlikte, eğer on milyon maddeyi sıralamanız gerektiğini tespit ederseniz, beklediğiniz şey, bu uygulama B'nin aslında, her bir algoritmanın ölçeklendirmesinin bir sonucu olarak, bu durumda, uygulama A'dan binlerce kez daha hızlı gerçekleşmesidir.


52
2018-01-28 13:12





İşte Big-O'nun ortak çeşitlerini açıklarken kullanacağım sade İngiliz bestiarı

Her durumda, listede daha yüksek olanlara listeden daha yüksek olan algoritmaları tercih edin. 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. Sorun ne kadar büyük olursa olsun, onu aynı miktarda çözebilirsiniz. Bu, yayın aralığına dahil olan insan sayısından bağımsız olarak, belirli bir mesafe üzerinden yayınlamak için aynı miktarda enerji harcadığı yayınlara benzemektedir.

O (giriş n):

Bu karmaşıklık aynıdır O (1) Sadece biraz daha kötü olması dışında. Tüm pratik amaçlar için, bunu çok büyük bir sabit ölçekleme olarak düşünebilirsiniz. 1 bin ile 1 milyar maddeyi işleme arasındaki iş farkı sadece altı faktördür.

O(n):

Sorunu çözmenin maliyeti problemin büyüklüğü ile orantılıdır. Sorununuz iki katına çıkarsa, çözümün maliyeti iki katına çıkar. Çoğu problemin bir şekilde bilgisayara, veri girişi, disk okur veya ağ trafiği olarak taranması gerektiğinden, bu genellikle uygun bir ölçeklendirme faktörüdür.

O(n kütük n):

Bu karmaşıklık çok benzer O(n). Tüm pratik amaçlar için, ikisi eşdeğerdir. Bu karmaşıklık düzeyi genellikle hala ölçeklenebilir olarak düşünülecektir. Bazı varsayımları yaparak O(n kütük n) algoritmalar dönüştürülebilir O(n) algoritmaları. Örneğin, tuşların boyutunu sınırlamak, sıralamayı O(n kütük n) için O(n).

O(n2):

Bir kare olarak büyür, nerede n bir karenin kenarının uzunluğudur. Bu, ağdaki herkesin ağdaki herkesi tanıyabildiği "ağ etkisi" ile aynı büyüme oranıdır. Büyüme pahalıdır. En ölçeklenebilir çözümler, anlamlı bir jimnastik yapmadan bu karmaşıklık düzeyindeki algoritmaları kullanamazlar. Bu genellikle tüm diğer polinom karmaşıklıkları için geçerlidir - O(nk) - de.

O (2n):

Ölçeklendirmez. Üç boyutlu olmayan bir problemi çözme umudunuz yok. Kaçınılması gerekenleri bilmek için uzmanlar ve uzmanlar için yaklaşık algoritmalar bulmak için O(nk).


35
2018-01-27 23:09



O (1) için farklı bir benzerlik düşünebilir misiniz? İçimdeki mühendis engellerden dolayı RF empedansı hakkında bir tartışma çıkarmak istiyor. - johnwbyrd
İyi bir sebeple "biraz" kelimesini kullandım. - Andrew Prock


Büyük O, bir algoritmanın, girişinin büyüklüğüne göre ne kadar zaman / alan kullandığını ölçer.

Bir algoritma O (n) ise, zaman / alan girişiyle aynı hızda artar.

Bir algoritma O (n ise2) o zaman zaman / alan girişinin karesi oranında artar.

ve bunun gibi.


34
2018-01-28 11:19



Uzay ile ilgili değil. Bu, zamanın anlamı karmaşıklık ile ilgili. - S.Lott
Her zaman zaman VEYA uzay hakkında olabileceğine inandım. ama ikisi de aynı anda değil. - Rocco
Karmaşıklık kesinlikle uzay hakkında olabilir. Şuna bir bak: en.wikipedia.org/wiki/PSPACE - Tom Crockett
Bu cevap, en "düz" olanıdır. Eskiden okuyucular onları anlamak için yeterince bilgi sahibi olduklarını varsayıyorlar ama yazarlar bunun farkında değiller. Onların onların basit ve sade olduğunu düşünüyorlar, ki bu kesinlikle değil. Oldukça formatlı bir metin yazmak ve CS olmayan kişiler için zor olan süslü yapay örnekler yapmak sade ve basit değil, çoğunlukla CS kişilerinin oy kullanabilmesi için çığır açanlar için çekici. Düz İngilizce'de CS teriminin açıklanması, kod ve matematik hakkında hiçbir şeye ihtiyaç duymaz. Bu cevap için +1 yine de yeterince iyi değil. - W.Sun
Bu cevap, f = O (g) nin f ve g'nin orantılı olduğu anlamına geldiği varsayımını (yaygın) hata yapar. - Paul Hankin