close
證明當f(n)=a0n0+a1n1+...+amnm=Big O(nm)
根據原式可知，f(n) = sigema(i 從0到m）的aknk
=sigema (i 從0到m）(|a0|n0+|a1|n1+...+|am|nm)
=sigema (i 從0到m）nm(|a0|n-m+|a1|nm-1+...+|am|n0)
=nm *sigema (i 從0到m）|ai|*1
其中，|ai|*1可視為常數項C
所以f(n)=nm
根據Big O的定義，當f(n)=O(g(n))的時候，必然存在一個C與n0
因此當f(n)=nm 時，C為2，取m=2，於n0時g(n） = 0(實際上無意義）
f(n) ＝ g(n），n2=0，符合
因此f(n)=a0n0+a1n1+...+amnm的Big O 為O(nm)
文章標籤
全站熱搜
留言列表
我想寫小說 (3)
