柚子快報激活碼778899分享：算法 【數據結構初階】復雜度
柚子快報激活碼778899分享：算法 【數據結構初階】復雜度
目錄
一、時間復雜度
????????1、時間復雜度的概念
? ??????2、大O的漸進表示法
????????3、常見的時間復雜度計算舉例
二、空間復雜度
????????1、空間復雜度的概念
????????2、常見的空間復雜度計算舉例
三、常見復雜度對比
正文開始——
前言
一個算法，并非越簡潔越好，那該如何衡量一個算法的好壞呢？看其復雜度。復雜度又分為時間復雜度和空間復雜度。
一、時間復雜度?
1.? 時間復雜度的概念?
在計算機科學中，算法的時間復雜度是一個函數，它定量描述了該算法的運行時間。一個算法執(zhí)行程序所消耗的時間，從理論上說，是不能算出來的，只有上機測試才能得知，于是我們有了時間復雜度這個分析方式。一個算法所花費的時間與其中語句的執(zhí)行次數成正比，算法中的基本操作的執(zhí)行次數，為算法的時間復雜度。
void Func1(int N)
{
int count = 0;
for (int i = 0; i < N ; ++ i)
{
for (int j = 0; j < N ; ++ j)
{
++count;
}
for (int k = 0; k < 2 * N ; ++ k)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d\n",count);
}
Func1執(zhí)行的基本次數：N^2+2*N+10
實際計算時間復雜度，我們不一定要精確計算執(zhí)行次數，只需要計算大概的執(zhí)行次數，那么這里我們使用大O的漸進表示法。
2.? 大O的漸進表示法?
大O符號：是用于描述函數漸進行為的數學符號。
推導大O階方法：
用常數1取代運行時間中的所有加法常數。在修改后的運行次數函數中，只保留最高階項。如果最高階項存在且不為1，則去除與這個項相乘的常數。得到的結果就是大O階。
so Func1的時間復雜度為：O（N^2）。通過上面我們發(fā)現大O的漸進法去掉了那些對結果影響不大的項，簡潔明了的表示出了執(zhí)行次數。
另外有些算法的時間復雜度存在最好、平均和最壞情況：
最壞情況：任意輸入規(guī)模的最大運行次數（上界）
平均情況：任意輸入規(guī)模的期望運行次數
最好情況：任意輸入規(guī)模的最小運行次數（下界）
例如：在一個長度為N數組中搜索一個數據x
最壞情況：N次找到
平均情況：N/2次找到
最好情況：1次找到
在實際中一般情況關注的是算法的最壞運行情況，所以數組中搜索數據x的時間復雜度為O（N）。
3.? 常見的時間復雜度計算舉例?
實例1：
//計算Func2的時間復雜度
void Func2(int N)
{
int count=0;
for(int k=0;k<2*N;k++)
{
++count;
}
int M=10;
while(M--)
{
++count;
}
printf("%d\n",count);
}
【解析】Func2執(zhí)行的基本次數：N*2+10 ，所以其時間復雜度為：O（N）。
實例2：
//計算Func3的時間復雜度
void Func3(int N,int M)
{
int count=0;
for(int k=0;k { ++count； } for(int k=0;k { ++count； } printf("%d\n",count); } 【解析】Func3執(zhí)行的基本次數：M+ N，有兩個未知數M，N，時間復雜度：O（M+N）。 實例3： //計算Func4的時間復雜度 void Func4(int N) { int count=0; for(int k=0;k<100;++k) { ++count; } printf("%d\n",count); } 【解析】Func4執(zhí)行的基本次數：100，對于常數一律用O（1）。 實例4： //計算strchr的時間復雜度 const char* strchr (const char* str,int character); 【解析】基本操作最好情況執(zhí)行1次，最壞N次，時間復雜度一般看最壞，時間復雜度為O（N）。 實例5： //計算BubbleSort的時間復雜度 void BubbleSort(int* a,int n) { assert(a); for(size_t end=n;end>0;--end) { int exchange=0; for(size_t i=1;i { if(a[i-1]>a[i]) { Swap(&a[i-1],&a[i]); exchange=1; } } if(exchange==0) break; } } 【解析】基本操作最好情況執(zhí)行N次，最壞執(zhí)行（N*（N+1））/2次，所以時間復雜度為O（N^2）. 實例6： int BinarySearch(int* a, int n, int x) { assert(a); int begin = 0; int end = n-1; // [begin, end]：begin和end是左閉右閉區(qū)間，因此有=號 while (begin <= end) { int mid = begin + ((end-begin)>>1); if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid-1; else return mid; } return -1; } 【解析】基本操作最好執(zhí)行1次，最壞O（logN）次，時間復雜度為O（logN）。ps：logN在算法分析中表示底數為2，對數為N。 實例7： // 計算階乘遞歸Fac的時間復雜度 long long Fac(size_t N) { if(0 == N) return 1; return Fac(N-1)*N; } 【解析】遞歸了N次，時間復雜度為O（N）。 實例8： // 計算斐波那契遞歸Fib的時間復雜度 long long Fib(size_t N) { if(N < 3) return 1; return Fib(N-1) + Fib(N-2) } 【解析】時間復雜度為O（2^N）。 二、空間復雜度? 1.? 空間復雜度的概念? 空間復雜度也是一個數學表達式，是對一個算法在運行過程中臨時占用存儲空間大小的量度。 空間復雜度不是程序占用了多少bytes的空間，因為這個也沒有太大意義，所以空間復雜度算的是變量的個數。空間復雜度計算規(guī)則與時間復雜度相似，也是用大O漸進表示法。 【注意】函數運行時所需要的棧空間（存儲函數、局部變量、一些寄存器信息等）在編譯期間已經確定好了，因此空間復雜度主要通過函數在運行時候?顯示申請的額外空間?來確定。 2.? 常見空間復雜度計算舉例? 實例1： // 計算BubbleSort的空間復雜度？ void BubbleSort(int* a, int n) { assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } } 【解析】 在函數運行過程中申請常數個額外空間，所以空間復雜度為O（1）。 實例2： // 計算Fibonacci的空間復雜度 // 返回斐波那契數列的前n項 long long* Fibonacci(size_t n) { if(n==0) return NULL; long long * fibArray = (long long *)malloc((n+1) * sizeof(long long)); fibArray[0] = 0; fibArray[1] = 1; for (int i = 2; i <= n ; ++i) { fibArray[i] = fibArray[i - 1] + fibArray [i - 2]; } return fibArray; } 【解析】 動態(tài)開辟了N個空間，所以空間復雜度為O（N）。 實例3： // 計算階乘遞歸Fac的空間復雜度 long long Fac(size_t N) { if(N == 0) return 1; return Fac(N-1)*N; } 【解析】遞歸調用了N次，開辟了N個棧幀，每個棧幀使用了常數個空間。空間復雜度為O（N）。 三、常見復雜度對比? 完—— ——————————————————? ?綠色? ?—————————————————— 綠色_陳雪凝_高音質在線試聽_綠色歌詞|歌曲下載_酷狗音樂酷狗音樂為您提供由陳雪凝演唱的高清音質無損綠色mp3在線聽,聽綠色,只來酷狗音樂!https://t4.kugou.com/song.html?id=7dQq7a4CPV2 ?你是否也期待來一場說走就走的旅行—— ?期待我們下一次的相遇—— 柚子快報激活碼778899分享：算法 【數據結構初階】復雜度 參考閱讀
本文內容根據網絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉載請注明，如有侵權，聯系刪除。
InstaShop即時出海購
