1.时间复杂度
时间复杂度主要衡量一个算法的运行快慢。
大O的渐进表示法
实例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;
}
}
准确的情况：n-1+n-2+n-3+.....+1=(n-1+1)*(n-1)/2
近似O(N^2);
实例2：
// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n - 1;
// [begin, end]：begin和end是左闭右闭区间，因此有=号
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;
}
二分查找
时间复杂度为O(logN);（以2为底）
2.空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。
大O的渐进表示法
复杂度的对比
//阶乘
long long Fac(size_t N)
{
if (0 == N)
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), 空间复杂度为O(N);
斐波那契数的时间复杂度为O(2^N), 空间复杂度为O(N);
(时间会叠加，而空间则会重复利用，当求完函数执行完成，函数的栈帧会销毁，但再次建立还是会重复使用这片区域)
举例说明：
#includevoid f1() { int a = 0; printf("%pn", &a); } void f2() { int a = 0; printf("%pn", &a); } int main() { f1(); f2(); return 0; }
地址一样，当函数完成时，栈帧会被销毁，但再次创建函数时，空间会再次使用，地址相同就是最好的证明。
3.复杂度的练习
1.面试题 17.04. 消失的数字--力扣
数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？
示例 1：
输入：[3,0,1]
输出：2
示例 2：
输入：[9,6,4,2,3,5,7,0,1]
输出：8
来源：力扣（LeetCode）
1.公式法
int missingNumber(int* nums, int numsSize){
int sum = 0;
sum = (0+numsSize)*(numsSize+1)/2;//首项加末项乘以项数除以2
int val = 0;
for(int i=0;i
1.公式法
时间复杂度为O(N),空间复杂度为O(1);
2.异或法
时间复杂度为O(N),空间复杂度为O(1);
3.开辟数组法
时间复杂度为O(N),空间复杂度为O(N);
4.排序+二分查找
时间复杂度过高
2. 189. 轮转数组------力扣
给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
示例 1:
输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]
来源：力扣（LeetCode）
//1.逐个转换
void reverse(int* nums, int i)
{
int val = nums[i];
int j = 0;
for (j = i; j >= 1; j--)
{
nums[j] = nums[j - 1];
}
nums[0] = val;
}
void rotate(int* nums, int numsSize, int k) {
int i = numsSize - 1;
while(i>=numsSize-k)
{
reverse(nums, numsSize-1);//每次交换一个数字
i--;
}
}
//2.递归
void reverse(int* nums, int left, int right)
{
while(left
1.逐个转换 时间复杂度O(N*K) 空间复杂度O(1);
2.递归 时间复杂度O(N) 空间复杂度O(1);
3.开辟数组 时间复杂度O(N）空间复杂度O(N);（以空间换时间）
