給表達式判斷時間複雜度

 下列小題時間複雜度是什麼

（一） 2022 n ln n+111 n^1.001

（二） 2022 n^3 2^n+111 n^2 3^n

 （三）2022 n!+2^n

（一）對於時間複雜度而言，n越大增長得越快。只看最大的表達式即可，因為如果只看小的會錯估，跟實際執行跑很慢對應不起來。如有一表達式為2^n+n!

2^n <--只看小的

|--| <--假設2^n資料量的可視化執行時間

n!    <--實際上執行時間會被它拖慢

|----------|<--n!的可視化執行時間

2022 n ln n+111 n^1.001

去掉常數項2022,111，比較n ln n 與n^1.001，n ln n可表示為nlogn ，nlogn比n^1.001增長快，所以時間複雜度是O(nlog n)

注意：ln=log

（二）

2022 n^3 2^n+111 n^2 3^n

去掉常數項2022,111，比較n^3 2^n與n^2 3^n，n^2 3^n增長比較快，所以時間複雜度為O(n^2 3^n)

（三）

2022 n!+2^n

去掉常數項2022，比較n!與2^n，n!增長比較快，所以時間複雜度為O(n!)

另一個題目

請用 Big-O 符號來表示下列函式的成長速率，並說明之：

T(n)=3n^3+7n^3n^0.5+n^3logn

解題關鍵：增長速度由慢至快 logn, n, nlogn, n^2

判斷n^3,n^3n^0.5,n^3logn哪個大？

n^3

n^3.5

n^3logn

n^3.5比n^3增長快

而n^3.5與n^3logn相比誰增長快？它們的不同在一個n^3乘n^0.5，另一個n^3乘logn ，因任一個正次方多項式都會增長比logn快，所以n^3.5會增長比n^3logn快。得增長由慢到快n^3logn, n^3, n^3.5。

答案是O(n^3.5)。