时间复杂度
时间复杂度描述了算法运行时间随输入规模增长的变化趋势。通常用大O符号（O）表示，忽略常数和低阶项，关注最高阶项。
常见时间复杂度
1. O(1)：常数时间复杂度，操作时间与输入规模无关。
2. O(log n)：对数时间复杂度，常见于二分查找。
3. O(n)：线性时间复杂度，操作时间与输入规模成正比。
4. O(n log n)：线性对数时间复杂度，常见于快速排序和归并排序。
5. O(n²)：平方时间复杂度，常见于简单排序算法如冒泡排序。
6. O(2^n)：指数时间复杂度，常见于某些递归算法。
7. O(n!)：阶乘时间复杂度，常见于排列组合问题。
大O的渐进表示法
大O的渐进表示法（Big O Notation）是用于描述算法时间复杂度和空间复杂度的一种数学符号。它表示算法在最坏情况下，运行时间或所需空间随输入规模增长的上界。大O表示法关注的是增长趋势，忽略常数因子和低阶项，只保留最高阶项。
大O表示法的特点
-
忽略常数因子：例如，O(2n) 简化为 O(n)。
-
忽略低阶项：例如，O(n² + n) 简化为 O(n²)。
-
描述上界：大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);
}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);
}void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++ k){++count;}printf("%d\n", count);
}// 计算strchr的时间复杂度？strchr用于字符串中查找特定字符的位置
const char * strchr ( const char * str, int character );//计算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;}}// 二分查找函数
int binarySearch(int arr[], int left, int right, int target) {while (left <= right) {int mid = left + (right - left) / 2;// 检查目标值是否在中间if (arr[mid] == target)return mid;// 如果目标值更大，忽略左半部分if (arr[mid] < target)left = mid + 1;// 如果目标值更小，忽略右半部分elseright = mid - 1;}// 如果未找到目标值，返回 -1return -1;
}// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{if(0 == N)return 1;return Fac(N-1)*N;
}// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{if(N < 3)return 1;return Fib(N-1) + Fib(N-2);
}空间复杂度
常见空间复杂度
1. O(1)：常数空间复杂度，算法所需空间固定，与输入规模无关。
2. O(n)：线性空间复杂度，算法所需空间与输入规模成正比。
3. O(n²)：平方空间复杂度，常见于某些二维数组操作。
分析下列实例的空间复杂度
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;}
}// 计算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;
}// 计算阶乘递归Fac的空间复杂度？
long long Fac(size_t N)
{if(N == 0)return 1;return Fac(N-1)*N;
}long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}函数的空间复杂度为 O(N)，主要由递归调用栈的深度决定。
例题
面试题 17.04. 消失的数字 - 力扣（LeetCode）
思路1：排序 再依次查找 如果下一个值不等于前一个值加一 则为消失的数字
时间复杂度分析：排序算法如qsort O(N*logN) + 遍历O(N) 时间复杂度太大 不合适
思路2：求和0到N 再依次减去数组中值 剩下的值则为消失的数字 时间复杂度O(N) 但是数字太大时候有溢出的风险
int missingNumber(vector<int>& nums) {int n =nums.size();int ret = (0+n)*(n+1)/2;for(int i = 0; i < n ; i++){ret -=nums[i];}return ret;}思路3：异或 相同的值异或后为0
//相同的值异或后结果为0
int missingNumber(int* nums, int numsSize)
{ int N = numsSize;int x = 0;for (int i = 0; i < N; i++){x ^= nums[i];}//异或0-n的数字for (int j = 0; j<= N; j++){x ^= j;}return x;
}
