舉個簡單的例子,評判一個算法的時間復雜度,那么下面 C 語言代碼的復雜度是多少呢?
i = 1;
while( i < n ){
i = i * 2;
}
對于此段代碼來說,我們只需要求出 while 循環(huán)中代碼(也就是第 3 行代碼)執(zhí)行的次數(shù),即可輕松得到這段代碼的時間復雜度?梢钥吹,循環(huán)條件為 i<n,而變量 i 的值每經(jīng)歷一次循環(huán)都會翻倍,因此假設有一個臨界值 m,能恰好使 2m = n,此時循環(huán)將會終止,程序運行結束。
求這段代碼的時間復雜度,只需要求出 m 的值即可。這就需要我們具備對數(shù)運算的能力。此時,如果讀者無法理解 m 值的由來,就需要惡補一下關于數(shù)學中對數(shù)運算的相關知識。
當然,對于絕大多數(shù)的數(shù)學運算,也可以借助計算器或者網(wǎng)絡工具來計算得出。事實上很多工作,我們完全不必親力親為,要善于運用網(wǎng)絡來解決遇到的難題。在實際開發(fā)中,很多網(wǎng)站都能提供幫助,例如 C++ 中可以使用 STL 標準庫,Python 中可以使用 collections 模塊等等。這意味著,我們的項目變成了已封裝好的模塊的組合應用,只需簡單了解各個模塊,即可實現(xiàn)最初的目的。