1

本 CLRS の 69 ページで、nC2 は単位分割統治法 (U - 4) の Θ(n^2) であると述べられています。この結果がどのように真実であるかを説明できる人はいますか?

4

1 に答える 1

6

nC2 = n*(n-1)/2 = (n^2-n)/2;

ヒント:

(n^2-n)/2c1*(n^2)のような定数c1 < 1/4や の値よりも大きくなりますn = 2。同様に、およびc2*n^2の値よりも小さくなります。これがサンドイッチのような状況です。同様に、n と定数 c の他の値についても挟まれます。したがって、.c2 = 1n = 2nC2 is Θ(n^2)

于 2014-06-20T11:12:27.810 に答える