In matematik , daha doğrusu içinde analiz , asimptotik karşılaştırma bir büyüme oranı üzerinde çalışmak içinde oluşan bir yöntemdir fonksiyonu içinde çevresinde daha "Basit" olarak ele alınan bir başka fonksiyonun bununla karşılaştırarak, bir noktanın ya sonsuzda. Bu genellikle , genellikle en azından belirli sözde temel fonksiyonları , özellikle polinomların , üstellerin ve logaritmaların toplamlarını ve ürünlerini içeren bir referans ölçeğinde seçilir . Karşılık gelen gösterimler özellikle fizikte ve bilgisayar biliminde , örneğin belirli algoritmaların karmaşıklığını tanımlamak için kullanılır . Analitik sayı teorisinde , asal sayıları sayma gibi düzensiz bir fonksiyonu seçilen ölçeğin bir fonksiyonu ile değiştirerek yapılan hatayı ince bir şekilde değerlendirmek için de kullanılırlar .
Yöntem, 1872'den Paul du Bois-Reymond'un çalışmasıyla tanıtıldı ; Hesaplamaları ve sonuçların sunumunu kolaylaştırmak için , özellikle Bachmann (1894), Landau (1909), Hardy (1910), Hardy ve Littlewood (1914 ve 1916) ve Vinogradov ( c. 1930) tarafından çeşitli gösterimler geliştirilmiştir .
Let f ve g olduğu formüller ile tanımlanan gerçek fonksiyonlar
İki fonksiyon üzerinde yapılan bir çalışmayla, g'nin sonsuz komşuluğunda istediğimiz kadar büyük değerler aldığını , f'nin ise sadece 1 ile 3 arasındaki değerleri alabildiğini biliyoruz. G bölü sonsuzun f au komşuluğuna bölünür. artmaya devam ediyor ve sınırlı değil. Bu bağlamda, biz söyleyebiliriz f olduğu içinde ihmal edilebilir önüne g ya da bu g olduğu önemli ağırlığı önünde f sonsuz mahalle, biz (Landau gösterimi) yazma:
veya (Hardy gösterimi, eski)
Hardy gösterimi üstünlük ilişkilerini zincirlemeyi mümkün kılar, örneğin:
G fonksiyonu kaybolmadığında biçimsel tanımBu özelliği resmi olarak tanımlamak için bölümün davranışını dikkate alıyoruz .
Dır-dir
F ve g , x gerçek değişkeninin iki fonksiyonu olsun . Biz farz gr bir mahalle üzerinde ortadan kalmadıysa bir . Biz söylemek f önünde önemsiz g ya da bu g olduğu önemli ağırlığı önünde f içinde bir ve biz not , ne zaman
Bağlam açıksa, çalışma alanı belirtilmez ve biri not edilir:, hatta . Bununla birlikte, gösterim her zaman bir yer a ve bu yerin mahallesi ile ilişkilendirilir : ihmal edilebilir olmak yerel bir kavramdır .
Bu Landau gösteriminde (bazen de ), sembol küçük o okur . Hardy'nin eşdeğer gösterimi . Bugün yalnızca Landau gösterimini kullanıyoruz.
ÖzellikleriDilin kötüye kullanılmasıyla , “küçük o” , yani önemsiz olanlar üzerinde “işlemler” yapılır . Nitekim şunu söyleyebiliriz:
Ya .
F ve g , x gerçek değişkeninin iki fonksiyonu olsun . Biz farz gr bir mahalle üzerinde ortadan kalmadıysa bir . Biz söylemek f eşdeğerdir g içinde bir ya da bu g eşdeğer f içinde bir ve biz göstermek
, ne zaman .Misal
Landau'nun büyük O gösterimi , bir işlevin diğerine göre baskın karakterini belirtir .
Genellikle, bu sembolü 1894'te tanıtan Paul Bachmann gibi biz de büyük O harfini kullanırız (Alman Ordnung'dan "düzen"). Çok daha sonra (1976), büyük omega sembolü Ω (aşağıya bakınız) ile benzerlik kurarak, Donald Knuth , O sembolünü büyük omikron harfinin adıyla yeniden adlandırmayı önerdi , ikincisi nadiren bu şekilde açık bir şekilde çizildi. O'dan farklı olarak her iki durumda da kullanılan sembol 0 (sıfır) sembolünden farklıdır.
Resmi tanımlamaF ve g , x gerçek değişkeninin iki fonksiyonu olsun . Bu demek f hakimdir g olarak ∞ + , ya da g ağırlıkta olmak f içinde + ∞ , ve göstermektedirler (Bachmann gösterim 1894, Landau, 1909)
veya (Hardy gösterimi, 1910, eski)
veya tekrar (Vinogradov notasyonu, 1930'lar)
N ve C sabitleri olduğunda
Sezgisel olarak bu, f'nin g'den daha hızlı büyümediği anlamına gelir .
Aynı şekilde, eğer a gerçek bir sayı ise, yazarız
d > 0 ve C sabitleri varsa öyle ki
Örnekler1914'te Hardy ve Littlewood , şu şekilde tanımlanan yeni sembolü Ω tanıttı:
.F ve g fonksiyonlarının sonsuz komşuluğunda tanımlandığı ve g pozitif olduğu varsayılır . Yani olumsuzlanmasıdır .
1916'da aynı yazarlar , aşağıdaki gibi tanımlanan iki yeni sembolü ( R ve Ω L) tanıttılar :
; .Daha önce olduğu gibi, f ve g fonksiyonlarının sonsuzluk komşuluğunda tanımlandığı ve g pozitif olduğu varsayılır . Yani, olumsuzlama ve olumsuzlama .
DE Knuth'un daha sonra iddia edeceğinin aksine , Edmund Landau bu üç sembolü 1924'te de kullandı.
Bu Hardy ve Littlewood notasyonları, Landau'dan sonra hiç bu şekilde kullanılmamış gibi görünen prototiplerdir: Ω R , Ω + ve Ω L , Ω - olmuştur .
Bu üç semboller artık yaygın olarak kullanılan analitik sayılar teorisi , hem de koşullar olduğunu belirtmek için ve hem koşullar sağlanır.
Tanımların her birinde biz yerini alabilir açıktır ∞ tarafından -∞ ya da gerçek sayısına göre.
Sahibiz
ve daha doğrusu,
Sahibiz
ve daha doğrusu,
ancak,
Yazının
Matematikte iki uyumsuz tanımı vardır, ikisi de çok yaygın, biri az önce sunduğumuz analitik sayı teorisinde , diğeri ise algoritmaların karmaşıklığı teorisinde . Bu iki disiplin bir araya geldiğinde, bu durumun büyük bir kafa karışıklığı yaratması muhtemeldir.
1976'da Knuth , Hardy ve Littlewood tarafından tarif edilenden farklı bir özelliği tanımlamak için aynı sembolü Ω kullanmasını haklı çıkarmak olan bir makale yayınladı. Okuyucuyu, Hardy ve Littlewood'un tanımının neredeyse hiç kullanılmadığına ikna etmeye çalışır (ki bu, 1976'da bile, 25 yıldır yanlıştır). Landau'nun onu hiç kullanmadığını iddia edecek kadar ileri gider (bu da yanlıştır). Zorunlu olarak başka bir fikre ihtiyaç olduğunu hissediyor ( " Bilgisayar bilimlerinde şimdiye kadar gördüğüm tüm uygulamalar için, daha güçlü bir gereksinim […] çok daha uygundur " ) ve Ω sembolünün kullanımının açıklamak için ayrılması gerektiğine karar verdi. o. O kuvvetle eski tanımı kızıyor ( “ Ne yazık ki, Hardy ve Littlewood tanımlamak vermedi Ω ( f ( n )) ben istedim olarak ” ).
Bu nedenle kafa karışıklığı yaratma riskini alır ve
.Matematikte, bir yaklaşımın hata terimine dikkat etmek genellikle önemlidir. Bu gösterim özellikle sınırlı gelişmeler ve eşdeğer hesaplamalarla uğraşırken kullanılır . Örneğin, üstel fonksiyonun 2. sıraya açılımı da yazılabilir:
Hata, fark gerçeğini ifade etmek için , önüne önemsizdir zaman 0 eğilimindedir.
Bu tür yazımdaki işlenenlerin sayısının , değişkene bağlı olmayan bir sabitle sınırlandırılması gerektiğine dikkat edilmelidir: örneğin, eğer elips, ne zaman sınırlı olmayan bir dizi terimi gizlerse , iddia açıkça yanlıştır. x değişir.
İşte analizde yaygın olarak kullanılan işlev kategorilerinin bir listesi. Değişken (burada n not edildi ) + ∞ olma eğilimindedir ve c keyfi bir gerçek sabittir. Tüm c 1'den büyük bir sabit büyüktür, işlevleri büyüklük artan sırada bu listede görüntülenir.
değerlendirme | en fazla boyut | |
O (1) | modül sabit arttı | |
O (günlük ( n )) | logaritmik | |
O ((günlük ( n )) c ) | ( polilogaritmik, eğer c pozitif tamsayı ise) | |
O ( n ) | doğrusal | |
O ( n günlük ( n )) | bazen " doğrusal " olarak adlandırılır | |
O ( n log c (n) ) | bazen " yarı doğrusal " olarak adlandırılır | |
O ( n 2 ) | ikinci dereceden | |
Y ( n c ) | ( Polinom ise C pozitif tam sayı olduğu) | |
O ( c n ) | ( üstel, eğer c pozitifse, bazen " geometrik ") | |
O ( n! ) | faktöryel |
O ( n c ) ve O ( c n ) çok farklıdır. İkincisi çok daha hızlı bir büyümeye izin verir ve bu herhangi bir sabit c > 1 için. Herhangi bir polinomdan daha hızlı artan bir fonksiyonun süperpolinom olduğu söylenir . Herhangi bir üstelden daha yavaş büyüyen bir fonksiyonun alt üstel olduğu söylenir . N log ( n ) işlevi gibi hem süperpolinom hem de alt üstel işlevler vardır .
Ayrıca, O (log n ) 'nin O (log ( n c ) ) ile tamamen aynı olduğuna dikkat edin , çünkü bu iki logaritma sabit bir faktörle birbirlerinden çokturlar ve büyük O gösterimi çarpım sabitlerini "yok sayar" . Benzer şekilde, farklı sabit tabanlardaki logaritmalar eşdeğerdir.
Yukarıdaki liste, aşağıdaki özellik nedeniyle kullanışlıdır: eğer bir fonksiyon f fonksiyonların toplamıysa ve toplamın fonksiyonlarından biri diğerlerinden daha hızlı büyürse, o zaman f ( n ) ' nin büyüme sırasını belirler .
Misal:
Eğer f ( n ), 10 günlük (= N ) + 5 (log ( n )) 3 + 7 N + 3 , n 2 + 6 , n 3 ,Bu gösterim, birkaç değişkenli işlevlerle de kullanılabilir:
Yazı : | ne zaman |
öneriye karşılık gelir: |
Bazıları için bu gösterim , eşitlik aksiyomunu ihlal ettiği için eşitlik sembolünü kötüye kullanır : "aynı olan şeyler birbirine eşittir" (diğer bir deyişle, bu gösterimle eşitlik n 'daha çok bir eşdeğerliktir. ilişki ). Ama bunu yazarken de düşünebiliriz
"= O" gösterimi, "=" işaretinin kendi bağımsız varoluşuna sahip olmadığı (ve özellikle bir eşdeğerlik ilişkisini belirtmediği) yazıdaki tek bir operatörü belirtir. Bu durumda, artık derecelendirmenin kötüye kullanılması söz konusu değildir, ancak açıkçası yine de bir kafa karışıklığı riski vardır. O ( g ( x )) 'i, elemanlarının tümü g'den daha hızlı büyümeyen işlevler olan bir dizi işlev olarak tanımlamak ve belirli bir işlevin kümenin bir öğesi olup olmadığını belirtmek için küme gösterimleri kullanmak da mümkündür. tanımlı. Örneğin :
Her iki anlaşmalar yaygın olarak kullanılan ancak ilk (ve en eski) başına kadar olan edilir XXI inci çoğunlukla yüzyıl karşılaştı. Bu problemden kaçınmak için (aynı sıklıkta) Vinogradov notasyonunu kullanıyoruz (aşağıya bakınız).
Diğer bir sorun, asimptotik davranışın incelendiği değişkeni açıkça belirtmenin gerekli olmasıdır. Gibi bir iddianın ardından "ne zaman " veya örneğin "(herhangi bir sabit için) ne zaman " gelip gelmediğine bağlı olarak aynı anlama gelmez .
Değerlendirme | Soyadı | Gayri resmi açıklama | Ne zaman , belli bir dereceden ... | Titiz tanım |
---|---|---|---|---|
veya
|
Grand O (Büyük Omicron) |
Fonksiyon | f | işlevi ile sınırlıdır | g | asimptotik olarak, |
Bir için k > 0 | |
veya
|
Büyük Omega |
İki tanım:
Sayı Teoride: |
Sayı teorisinde: Bir için k > 0 |
Sayı teorisinde:
|
Algoritma teorisinde:
f , g ile hafife alınır (bir faktöre kadar) |
Algoritma teorisinde:
Bir için k > 0 |
Algoritma teorisinde:
|
||
sırasına göre; Büyük Theta |
f hakimdir veasimptotik olarak g'ye maruz kalır |
bir k 1 > 0 ve bir k 2 > 0 için |
|
|
veya
|
Küçük o | f asimptotik olarak g'nin önünde ihmal edilebilir | , ne olursa olsun > 0 (sabit). | |
Küçük Omega | f g'ye asimptotik olarak hakimdir | tüm k > 0 | ||
eşittir | f ,asimptotik olarak g'ye yaklaşık olarak eşittir | , ne olursa olsun > 0 (sabit). |
Grand-O'dan sonra, Θ ve Ω gösterimleri bilgisayar biliminde en çok kullanılanlardır; small-o matematikte yaygındır ancak bilgisayar bilimlerinde daha nadirdir. Ω çok az kullanılır.
Bilgisayar bilimlerinde bazen kullanılan başka bir gösterim Õ'dir ( İngilizce'de soft-O ), bu da poli-logaritmik faktöre kadar büyük-o anlamına gelir.
Sayı teorisinde f ( x ) g ( x ) notasyonu , f ( x ) = Θ ( g ( x )) (kullanılmayan) ile aynı anlama sahiptir .
Landau gösterimler konusunda uzmanlaşmış Alman matematikçi adını sayılar teorisi Edmund Landau sembolü kullanılan O başlangıçta tarafından tanıtılan, Paul Bachmann ve sembol icat ilham o . O sadece 1924 yılında bir makalede sembol Q'dan kullanılan e delalet ≠ o ; bu notasyon (aynı anlamla) 1914'te GH Hardy ve JE Littlewood tarafından tanıtıldı; O zamandan beri, Ω yaygın olarak sayı teorisinde kullanılır, ancak yalnızca bu aynı anlamda ve hiçbir zaman yukarıdaki tabloda ilk anlamda gösterilmemiştir. Aynı makalede Landau sembolleri Ω kullanır R ve Ω L , aynı zamanda, Hardy ve Littlewood için (ve belirtilen Ω beri + ve Q - belirtmek için) , sırasıyla . Elbette, not gösterimini de kullanır, ancak asla never veya ω gösterimini kullanır.
Hardy notasyonları et getirdiği, GH Hardy 1910 onun yollarında Infinity Siparişleri , asimtotik karşılaştırma için Landau aynıdır rol oynamaktadır.
Landau gösteriminde bunları şu şekilde tanımlayabiliriz:
ve
Hardy'nin reytingleri geçerliliğini yitirdi. Hardy hızla kendi reytinglerinden vazgeçti; 1910 ve 3 makalesi (1910-1913) hariç tüm makalelerinde (yaklaşık 400!) ve kitaplarında Landau'nun notasyonlarını kullanır. Hardy, 1910 tarihli yazısında, fonksiyonların asimptotik karşılaştırması için başka semboller sunduysa, Vinogradov'a borçlu olduğumuz gösterimi (veya ) hiçbir zaman tanımlamadı veya kullanmadı .
Rus sayı teorisyeni Ivan Matveyevich Vinogradov , 1930'larda adını taşıyan notasyonu tanıttı.
.Vinogradov'un ≪ gösterimi genellikle O yerine sayı teorisinde kullanılır ; bazen iki notasyon bile aynı makalede birbirinin yerine kullanılır.
1982'de Carl Pomerance , algoritmaların karmaşıklığının asimptotik çalışmasında yer alan karmaşık işlevleri kısaltmak için yeni bir gösterim sundu . Öyleyse, örneğin, bir f fonksiyonu , eğer sahipsek sınıfa aittir ; üstel, işlevleri yeterince "ayırır", böylece bu gösterimi, örneğin forma indirgemek mümkün değildir .
Özellikle Landau derecelendirmeleri, yazma veya daha kötüsü gibi çok sık derecelendirme kötüye kullanımına yol açar ; Bu ikinci notasyonu bir dizi dil kullanarak okumak gerekir: arayarak kıyasla ihmal fonksiyonların kümesini ve iki fonksiyonlarının farklılıkların seti , bu demektir . Daha genel olarak, gösterimin bu kötüye kullanılması, gösterimi (veya , vb.) Bir işlevler sınıfını temsil ettiği ve bu sınıfa ait bir anlam olarak ele alınması anlamına gelir .
(tr) Big-O Cheat Sheet , etki alanına göre algoritmik karmaşıklıkların sınıflandırılmasını listeleyen bir site.
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">