一.时间复杂度
定义：程序运行的快慢，时间复杂度是数学里带有未知数的函数表达式（！=c语言里的函数）
注意：由于环境的不同，所以具体的运算时间也不同，因此时间复杂度计算的是执行次数
eg：F（N）=N*N+2*N+10；
--->取对函数值影响最大的项出来：F（N）=N^2 （该部分就是所要求的时间复杂度）
N=10-->F(N)=100;
N=100-->F(N)=10000;
由观察可得：N越大，后两项对函数值的影响越小
计算时间复杂度不是精确次数，而是大概的执行次数，使用大o渐进表示法（即：求极限法/估算）
总结：
1.当M远大于N-->时间复杂度为o（M）；
2.当N远大于M-->时间复杂度为o（N）；
3.当M和N差不多大-->时间复杂度为o（M）/o(N)；
4.当未说明M，N的大小-->时间复杂度为o（M+N）；
5.常数循环的时间复杂度为：o（1）；
（将时间复杂度调整为o（1），即只能进行常数次循环）--->1代表所有的常数
example：
（1）求库函数strchar的时间复杂度：
该函数的具体实现过程：
//strchar的实现过程
//在数组中找寻所选定的字符
while (*str)
{
if (*str == character)
{
return str;
}
else
++str;
}
（2）冒泡排序的时间复杂度：
//回顾冒泡排序
for (i = 0; i < sz - 1; i++)
{
for (j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
时间复杂度不能只看是几层循环，还要去看它的思想
（3）二分查找的时间复杂度：
//回顾二分查找
#include <iostream>
using namespace std;
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9,10 };
int k = 7;
int sz = 0;
sz = sizeof(arr) / sizeof(arr[0]);
int left = 0;
int right = sz - 1;
while (left <= right)
{
int mid = 0;
mid = left + (right - left) / 2;
if (arr[mid] < k)
{
left = mid + 1;
}
else if (arr[mid] > k)
{
right = mid - 1;
}
else
{
cout << "找到了，下标是：" << mid << endl;
break;
}
if (left > right)
{
cout << "找不到" << endl;
}
}
return 0;
} 
(4)递归的时间复杂度
（5）斐波那契递归Fib时间复杂度
时间复杂度：o(2^N)
二.空间复杂度
(数学函数表达式)
定义：程序运行所需要的额外空间大小（即变量的个数）
（1）冒泡排序的空间复杂度
--->每次递归调用完后所使用的空间都会继续循环使用，用完即销毁
--->空间复杂度:o(1)
（2）递归（上述求时间复杂度的题（4））的空间复杂度
栈帧的消耗大于递归的深度
--->空间复杂度：o(N)
（3）斐波那契的空间复杂度
--->空间复杂度：o(N)
总结：
1.空间是可以重复利用，不累计的
2.时间是一去不复返，累计的
三.例题
1.
//消失的数字
#include <iostream>
using namespace std;
int missingNumber(int* nums,int sz)
{
int x = 0;
int i = 0;
for (i = 0; i <=sz; i++)
{
x ^= i;
}
for (i = 0; i < sz; i++)
{
x ^= nums[i];
}
return x;
}
void test01()
{
int nums[] = { 0,1,3,4,5,6,7,8,9 };
int sz = 0;
sz = sizeof(nums) / sizeof(nums[0]);
int ret = 0;
ret = missingNumber(nums, sz);
cout << "消失的数字为：" << ret << endl;
}
int main()
{
test01();
return 0;
}2.
//旋转数组
#include <iostream>
using namespace std;
void Reverse(int* nums, int left, int right)//逆置
{
while (left < right)
{
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
void rotate(int* nums, int sz, int k)//k为旋转的次数
{
if (k >= sz)//当旋转的次数等于数组元素个数时，不旋转即使要求的结果
{
k %= sz;
}
Reverse(nums, 0, sz - k - 1);//将前（n-k）个逆置
Reverse(nums, sz - k, sz - 1);//将后k个逆置
Reverse(nums, 0, sz - 1);//将整体逆置
}
void test01()
{
int nums[] = { 1,2,3,4,5,6,7 };
int sz = sizeof(nums) / sizeof(nums[0]);
rotate(nums, sz, 3);
for (int i = 0; i < sz; i++)
{
cout << nums[i] << " ";
}
cout << endl;
}
int main()
{
test01();
return 0;
}--->运行结果：
