Big Oh notasyonu

Question

Sadece hızlı bir şekilde bir şey teyit gerekir. Bir algoritma çalıştırmak için n(n-1)/2 testleri alırsa, büyük O(n^2) nedir?

Answer 1

n (n-1)/2 genişler (n^2 -n)/2 için olması bir c almak durumunda tüm n>=1 için c*n^2 açıkça daha küçük olan, (n^2 - n)/2, yani (n^2/2) - (n/2)

(n^2/2) ve (n/2) olmasıdır n^2/2'un baskın olduğu iki işlev bileşeni. Bu nedenle, - (n/2) parçasını yok sayabiliriz.

n^2/2'dan itibaren asimptotik notasyon analizinde/2 parçasını güvenle kaldırabilirsiniz.

Bu nedenle evet, O ise n^2

için yardım (^ 2 n)

Answer 2

Evet, bu doğru.

n(n-1)/2n^2/2 - n/2 genişler:

alt düzenin çünkü devre dışı bırakır n/2 doğrusal bir terimdir. Bu n^2/2 bırakır. Sabit, n^2'u bırakarak büyük O içine emilir.

Answer 3

Evet:

n(n-1)/2 = (n2-n)/2 = O(n^2) 

Answer 4

Evet, öyle. n(n-1)/2 en az 1