1、時間復(fù)雜度和空間復(fù)雜度

（1）時間復(fù)雜度、空間復(fù)雜度是什么？

• 算法效率分析分為兩種：第一種是時間效率，第二種是空間效率。
• 時間效率被稱為時間復(fù)雜度，空間效率被稱作空間復(fù)雜度
• 時間復(fù)雜度主要衡量的是一個算法的運(yùn)行速度，而空間復(fù)雜度主要衡量一個算法所需要的額外空間
• 在計算機(jī)發(fā)展的早期，計算機(jī)的存儲容量很小。所以對空間復(fù)雜度很是在乎。但是經(jīng)過計算機(jī)行業(yè)的迅速發(fā)展，計算機(jī)的存儲容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個算法的空間復(fù)雜度，如今更加考慮時間復(fù)雜度

（2）時間復(fù)雜度的計算

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);
}//實際執(zhí)行N * N + 2 * N + 10

①代碼解析

實際的們計算時間復(fù)雜度的時候，不用計算如此精確的執(zhí)行次數(shù)，于是這里我們使用大O漸進(jìn)表示法，時間復(fù)雜度不算時間，算次數(shù)

②大O表示法

是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號

③推導(dǎo)方法

• 用常數(shù)1取代運(yùn)行時間中的所有加法常數(shù)
• 在修改后的運(yùn)行函數(shù)中，只保留最高階項
• 如果高階項存在且不是1，則去除于這個項目相乘的常數(shù)

④最好、平均、最壞情況：

• 最好情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)（上界）
• 平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)
• 最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)（下界）

⑤推導(dǎo)例子

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);
}
//2 * N + 10 ====> O(N)

void Func3(int N, int M)
{int count = 0;for (int k = 0; k < M; ++ k){++count;}for (int k = 0; k < N ; ++ k){++count;    }printf("%d\n", count);
}
//M + N====>O(M + N)
//如果M遠(yuǎn)大于N====>O(M)
//如果M、N相差不大====>O(2 * M)/O(2 * N)====>O(M)/O(N)

void Func4(int N)//N沒有用到，時間復(fù)雜度與N無關(guān)
{int count = 0;for (int k = 0; k < 100; ++ k){++count;}printf("%d\n", count);
}
//100====>O(1)，反過來就說明輸入數(shù)據(jù)了常數(shù)次

//計算strchr的時間復(fù)雜度？
const char * strchr ( const char * str, char character )
{while(*str != '\0'){if(*str == character)return str;++str;}return NULL;
}
//需要分情況：最壞、平均、最好，假設(shè)字符串長度為N
//最壞的沒有找到或者在最后找到====>O(N)
//平均就是O(N / 2)
//最壞就是O(1)
//當(dāng)要分情況的時候要用最壞的情況表示，因此最終結(jié)果就是O(N)  

// 計算BubbleSort的時間復(fù)雜度？（冒泡排序）
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]);//調(diào)換兩個元素exchange = 1;}}if (exchange == 0)break;}
}
//這個也要分情況
//第一次冒泡N次（也可以理解為N - 1的）
//第二次冒泡N - 1次
//……
//第N次冒泡1次
//和為((1 + N) * N) / 2
//因此最壞情況O(N^2)

// 計算BinarySearch的時間復(fù)雜度？（二分查找法）
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n;while (begin < end){int mid = begin + ((end-begin) >> 1);//求平均值if (a[mid] < x){    begin = mid+1;}else if (a[mid] > x){end = mid;}else{return mid;}}return -1;
}
//這個也要分情況
//O(log(2)N)簡寫為log(N)，最好不要寫lg(N)盡管有的地方會這樣寫，詳細(xì)解說在下面

// 計算階乘遞歸Factorial的時間復(fù)雜度？
long long Factorial(size_t N)
{return N < 2 ? N : Factorial(N-1) * N;
}
//Factorial(10)
//Factorial(9) * 10
//Factorial(8) * 9
//……
//Factorial(1) * 2
遞歸了N次，每次就是O(1)，整體就是O(N)
//如果假設(shè)遞歸內(nèi)用的是循環(huán)語句for(int i = 0; i < N; ++i);則每次是O(N)，整體就是O(N^2)

⑥常見的時間復(fù)雜度對比

O(1) < O(logN) < O(N) < O(N^2)

（3）空間復(fù)雜度的計算

// 計算BubbleSort的空間復(fù)雜度？
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;}
}
//標(biāo)粗的地方占用了變量，即5====>O(1)
//注意時間是累積的，空間是不累積的（因為重復(fù)利用了一個空間）

①代碼解析

實際的們計算空間復(fù)雜度的時候，也不用計算如此精確的空間，只需要知道大概的執(zhí)行次數(shù)即可，于是這里我們也同樣使用大O漸進(jìn)表示法，空間復(fù)雜度不算空間，算變量個數(shù)

②大O表示法

是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號

③推導(dǎo)方法

• 用常數(shù)1取代運(yùn)行時間中的所有加法常數(shù)
• 在修改后的運(yùn)行函數(shù)中，只保留最高階項
• 如果高階項存在且不是1，則去除于這個項目相乘的常數(shù)

④推導(dǎo)例子

// 計算Fibonacci的空間復(fù)雜度？（斐波那契數(shù)列）
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;
}
//O(N + 6)====>O(N)
//雖然大部分算法的空間復(fù)雜度都是O(1)

// 計算階乘遞歸Factorial的空間復(fù)雜度？
long long Factorial(size_t N)
{return N < 2 ? N : Factorial(N - 1) * N;
}
//遞歸調(diào)用了n層，每次調(diào)用建立一個棧幀，每次使用了常數(shù)O(1)，整體就是O(N)

2、有關(guān)的練習(xí)題目

（1）面試題 17.04. 消失的數(shù)字 - 力扣（LeetCode）

//思路一：
int missingNumber(int* nums, int numsSize)
{int add_1 = 0;int add_2 = 0;add_1 = ( (0 + numsSize) * (numsSize + 1) ) / 2;for(int i = 0; i < numsSize; i++){add_2 += nums[i];}return add_1 - add_2;
}

//思路二：
int missingNumber(int* nums, int numsSize)
{int x = 0;int i = 0;for(i = 0; i < numsSize; i++)//用for循環(huán)求出數(shù)組nums元素的異或和{x ^= nums[i];}for(i = 0; i < numsSize + 1; i++)//運(yùn)用異或的性質(zhì)a^a=0來找出消失的數(shù)字{x ^= i;}return x;
}

（2）189. 輪轉(zhuǎn)數(shù)組 - 力扣（LeetCode）

//思路一：
void rotate(int* nums, int numsSize, int k)
{while(k--){int tmp = nums[numsSize - 1];//保留最后一個數(shù)字for(int end = numsSize - 2; end >= 0; --end)//開始將最后一個數(shù)字前面的所有數(shù)字后移{nums[end + 1] = nums[end];}nums[0] = tmp;}
}
//但是超出了時間限制

//思路二：
void Reverse(int* nums, int left, int right)
{while(left < right)//奇數(shù)個會相等，偶數(shù)個會錯開{int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;++left;--right;}
}
void rotate(int* nums, int numsSize, int k)
{if(k >= numsSize)//防止k大于數(shù)組大小，例如7個元素旋轉(zhuǎn)13次和6次等價{k %= numsSize;}Reverse(nums, numsSize - k, numsSize - 1);//后半部分Reverse(nums, 0, numsSize - k - 1);//前半部分Reverse(nums, 0, numsSize - 1);
}