i Big-O Notasyonu'nu

kullanarak karmaşıklığı belirlemek nasıl

Benim ihtiyacım, burada birkaç örnek ve beni Big-O Gösterimi kullanarak karmaşıklığı bulmanıza yardımcı olabilir umut bunu belirleme konusunda bir açıklama şudur:i Big-O Notasyonu'nu

For each of the following, find the dominant term(s) having the sharpest increase in n and give the time complexity using Big-O notation. 
Consider that we always have n>m. 

Expression Dominant term(s) O(…) 
5+ 0.01n^3 + 25m^3 
500n +100n^1.5 + 50nlogn 
0.3n+ 5n^1.5 +2.5n^1.75 
n^2logn +n(log2m)^2  
mlog3n +nlog2n 
50n+5^3 m + 0.01n^2

kaynak

2016-04-14 Anonymous

Büyük O'nun, okuyabileceğiniz veya okuyamadığınız birkaç açıklaması vardır. [Büyük O, nasıl hesaplarsınız] (http://stackoverflow.com/questions/3255/big-o-how-do-you-calculate-approximate-it?rq=1) ve [O Big O düz İngilizce açıklama ] (http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o?rq=1). Sorulan sorunun geri kalanı, sizin için ev ödevi gibi görünen bir şeyi yapmak için burada. – KevinO

Bu soruyu off-topic olarak kapatmak için oy veriyorum çünkü, teorik bir soru olarak, Bilgisayar Bilimleri gibi bir siteye aittir. –

Oldukça basit.

n büyük sayılara (sonsuza doğru) yükseldikçe, ifadenin bazı kısımları anlamsız hale gelir, bu nedenle bunları kaldırın. Ayrıca, O() notasyonu göreceli değil, mutlaktır, anlamsızdır, yani ölçek yoktur, bu yüzden sabit faktörler anlamsızdır, bu nedenle bunları kaldırın.

Örnek: 100 + 2*n. Düşük sayılarda 100 sonuca ana katkıda bulunur, ancak n arttıkça anlamsızlaşır. Ölçek olmadığından, n ve 2n aynı şeydir, yani doğrusal bir eğridir, bu nedenle sonuç O(n) olur. http://bigocheatsheet.com/img/big-o-complexity.png

senin ikinci bir örneği ele alalım: 500n +100n^1.5 + 50nlogn
1 kısım O(n) olduğunu

Veya, bu grafikten ifadede en aşırı eğri başka bir yol seçmek söyledi.
2. kısım O(n^1.5)'dur.
3. kısım O(nlogn)'dur.
En hızlı yükselen eğri O(n^1.5), yani cevap budur.

kaynak

2016-04-14 16:49:12 Andreas

Detaylı cevabınız için çok teşekkür ederim, gerçekten bazı adımları anlamaya yardımcı oldu, fakat gördüğünüz gibi, farklı türlerimiz ve başka bir değişkenin olduğu başka örnekler de vardır [m]. Diğer durumlarda nasıl hesaplayabilirim? Tekrar teşekkürler. –

Senin için tüm ödevlerini yapmayacağım. Belki bu bölümü okumalısınız: https://en.wikipedia.org/wiki/Big_O_notation#Properties – Andreas

@Moudi diğer değişken, aynı kuralları izleyerek kendi boyutudur. Yani ilk olan O olur (n^3 + m^3) – Carlos

i Big-O Notasyonu'nu

cevap

İlgili konular