斐波那契數 時間，空間復雜度
- 大O的漸進表示法
- 推導大O階方法：
- 時間復雜度
- 時間復雜度的概念
- 空間復雜度
- 空間復雜度的概念
大O的漸進表示法
推導大O階方法：
1、用常數1取代運行時間中的所有加法常數，
2、在修改后的運行次數函式中，只保留最高階項，
3、如果最高階項存在且不是1，則去除與這個專案相乘的常數，得到的結果就是大O階，
注意：有些演算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規模的最大運行次數(上界)
平均情況：任意輸入規模的期望運行次數
最好情況：任意輸入規模的最小運行次數(下界)
例如：在一個長度為N陣列中搜索一個資料x
最好情況：1次找到
最壞情況：N次找到
平均情況：N/2次找到
在實際中一般情況關注的是演算法的最壞運行情況，所以陣列中搜索資料時間復雜度為O(N)
時間復雜度
時間復雜度的概念
時間復雜度的定義：在計算機科學中，演算法的時間復雜度是一個函式，它定量描述了該演算法的運行時間，一個演算法執行所耗費的時間，從理論上說，是不能算出來的，只有你把你的程式放在機器上跑起來，才能知道，但是我們需要每個演算法都上機測驗嗎？是可以都上機測驗，但是這很麻煩，所以才有了時間復雜度這個分析方式，一個演算法所花費的時間與其中陳述句的執行次數成正比例，演算法中的基本操作的執行次數，為演算法的時間復雜度，
遞回演算法的時間復雜度：遞回的總次數*每次遞回的數量，
斐波那契數列，又稱黃金分割數列，指的是這樣一個數列：0、1、1、2、3、5、8、13、21、34、……
遞回求斐波那契數時間復雜度為O(2^N)
時間復雜度分析：
求解F(n),必須先計算F(n-1)和F(n-2),計算F(n-1)和F(n-2)，又必須先計算F(n-3)和F(n-4)…以此類推，直至必須先計算F(1)和F(0),然后逆推得到F(n-1)和F(n-2)的結果，從而得到F(n)要計算很多重復的值，在時間上造成了很大的浪費，演算法的時間復雜度隨著N的增大呈現指數增長，時間的復雜度為O(2^n)，即2的n次方
long long Fib(size_t N)
{
return N < 2 ? N : Fib(N - 1) + Fib(N - 2);
}
這種方法看似代碼簡單，實際操作起來非常繁瑣,有興趣的朋友可是試試給個100運行一下，不過可能得等上幾個小時才會出結果哦
遞回求斐波那契數時間復雜度為O(N)
尾遞回法
如果一個函式中所有遞回形式的呼叫都出現在函式的末尾，我們稱這個遞回函式是尾遞回的，當遞回呼叫是整個函式體中最后執行的陳述句且它的回傳值不屬于運算式的一部分時，這個遞回呼叫就是尾遞回，
long long Fib(long long first, long long second, long long n)
{
if (n < 3)
return 1;
if (3 == n)
{
return first + second;
}
return Fib(second, first + second, n - 1);
}
用回圈方法來實作時間復雜度為O（N)的斐波那契數
long long Fib(int n)
{
long long ret = 0;
long long first = 1, second = 1;
for (int i = 3; i <= n; i++)
{
ret = first + second;
first = second;
second = ret;
}
return ret;
}
空間復雜度
空間復雜度的概念
空間復雜度是對一個演算法在運行程序中臨時占用存盤空間大小的量度 ，=空間復雜度算的是變數的個數，空間復雜度計算規則基本跟時間復雜度類似，也使用大O漸進表示法，
遞回演算法的空間復雜度：遞回的深度*每次遞回創建變數的個數，
空間復雜度為O（N)的斐波那契數
long long Fib(int n)
{
long long*p = (long long*)malloc(sizeof(long long)*n);
assert(p != NULL);
p[0] = 1, p[1] = 1;
for (int i = 2; i < n; i++)
{
p[i] = p[i - 1] + p[i - 2];
}
long long ret = p[n - 1]; //定義一個臨時變數去接收p[n-1],以便于最后釋放這個記憶體空間
free(p);
return ret;
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/282114.html
標籤：其他
上一篇：獨立按鍵控制直流電機轉動
下一篇：2021春招實習面經——開發方向