悟的复杂度分析
复杂度分析：
时间复杂度（算法中的基本操作的执行次数）；
空间复杂度。
时间复杂度：
实际上我们计算时间复杂度时，我们其实并不需要计算准确的执行次数，只需要大概的执行次数，因此我们在这里使用大O的渐进表示法。常见的时间复杂度O（1）， O（N²）， O（N）， O（logN）。
大O符号：
是用于描述函数渐进行为的数学符号。
推导大O阶方法：
1.用常数1取代运行时间中的所有加法常数；
例：
计算下面代码的时间复杂度
void f(int N)
{int count = 0;for(int k = 0; k < 100; ++k){++count;}
}答案：O（1）
注：确定的常数次，都是O（1）。
2.在修改后的运行次数函数中，只保留最高阶项；
例：
计算下面代码的时间复杂度
void f(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", count);
}答案：O（N²）
注：准确的执行次数：N² + 2 * N + 10
随着N的增大，这个表达式中N²对结果的影响最大
3.若最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶。
例：
计算下面代码的时间复杂度
void f(int N)
{int count = 0;for (int k = 0; k < 2 * N; ++k){count++;}int M = 10;while (M--){++count;}printf("%d", count);
}答案：O（N）
特殊情况：
例一：
计算下面代码的时间复杂度
void f(int N, int M)
{int count = 0;for (int k = 0; k < N; k++){++count;}for (int k = 0; k < M; k++){++count;}
}答案：O（M + N）
注：假如给了条件：M远大于N，答案是O（M）；M和N差不多大，O（M）或O（N）。
例二：
计算下面代码的时间复杂度
const char* s(const char* str, char cha)
{while (*str != '\0'){if (*str == cha){return str;}++str;}return NULL;
}假设字符串长度是N。
答案：O（N）
注：有些算法的时间复杂度存在最好，平均，最坏情况：
最坏：O（N）
平均：O（N/2）
最好：O（1）
在实际中一般情况关注的是算法的最坏运行情况。
例三：
计算下面代码的时间复杂度
void B(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){break;}}
}答案：O（N²）
注：第一趟冒泡：N
第二趟冒泡：N - 1
........
第N趟：1
以上是个等差数列，所以准确的次数是（N+1）*N/2
时间复杂度为O（N²）
例四：
计算下面代码的时间复杂度
int B(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（logN）
注：假设找了X次
2的X的平方 = N
X=logN
因为有很多地方不好写底数，所以一般省略简写成logN。
例五：
计算下面代码的时间复杂度
long long f(size_t N)
{return N < 2 ? N : f(N - 1) * N;
}答案：O（N²）
注：递归调用了N次，每次递归运算--》O（1）
整体就是O（N）。