一起来学数据结构——时间复杂度和空间复杂度
时间复杂度
概念
算法中基本操作的执行次数，就是时间复杂度。（注意：不是运行所需要的时间)
如何计算时间复杂度
实例1
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);
}
func1的基本执行次数为F(N)=N^2+2*N+10
当N=10时，F（N）=130
当N=100时，F（N）＝１０２１０
当N＝１０００时，F（N）＝１００２０１０
但是，当我们计算时间复杂度的时候，实际上不需要具体的，详细的执行次数，我们只需要知道大概的执行次数就可以了，所以我们采用大O的渐进表示法。
大O符号：用于计算函数渐进行为的符号
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶
则ｆｕｎｃ１的时间复杂度为O（N＾２）,去掉了对执行次数影响不大的次数，这就是渐进的大O阶方法。
实例2：
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);
}
根据大O阶方法：func2(N)=2*N+10,根据
3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶
所以：F（N）=O（N）
实例3：
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;
}
由于N和M都是变化的，所以func3的时间复杂度就是：O（M+N）
实例4：
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
根据大O阶方法
1、用常数1取代运行时间中的所有加法常数
所以func4的执行次数是100，但是和N是没有任何关系的，所以无论N怎么变化，func4的时间复杂度都是O（1）
实例5：
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
下面是在一个字符串中查找是否能找到一个指定的字符，如在字符串"abcdef"中找
const char * strchr ( const char * str, char character )
{
while(*str != '\0')
{
if(*str == character)
return str;
++str;
}
return NULL;
}
‘a’,是最好的情况，只需要查找1次 O（1）
’f’,是最坏的情况，需要查找6次 O（N）
‘c’,是平均的情况，需要查找3次 O（N/2）
这时我们要取哪个作为我们的时间复杂度呢？
根据大O阶方法：
在实际中一般情况关注的是算法的最坏运行情况
所以strchr的时间复杂度就是：O（N）
实例6：
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
最坏是：ｎ＋ｎ－１＋ｎ－２＋ｎ－３＋．．．＋１＝ｎ＊（ｎ－１）／２，
所以根据大O阶方法+一般看最坏，该函数的时间复杂度是
O（N＾２）
实例7：
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;
}
该函数的执行次数是
最好是：1
最坏是：
以ａｒｒ［８］＝｛１，２，３，４，５，６，７，８｝来查找１１
第一次：４＜１１，５～８
第二次：６＜１１，７～８
第三次：７＜１１，８～８
３＝log（８）
所以最坏的执行的次数为O（logN）
所以根据大O阶方法+一般看最坏，该函数的时间复杂度是
O（ｌｇN）logN是以2为底的对数
实例8：
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
根据递归的知识，我们会发现执行次序是N-2，即时间复杂度为O（N）
总结
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-jWUMvC2J-1630418921051)(C:\Users\19625\AppData\Roaming\Typora\typora-user-images\image-20210821230824534.png)]
右侧，从上至下，时间复杂度依次增大。其中O（1）和O（logN）的效果是一样的
空间复杂度
概念
空间复杂度也不是计算开辟空间的具体大小的，不是看它具体暂居多少byte的内存，而是看它所创建变量的个数，和时间复杂度一样，它也采用大O渐进表示法来表示
如何计算空间复杂度
和时间复杂度的计算方法大同小异，常数的部分忽略，主要看变量的创建N。
实例1
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;
}
}
认真的数一数，我们会发现只创建了3个变量，所以空间复杂度是O（1）
实例2
隐藏于malloc里面的动态变量的创建
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 ;
}
根据仔细的观察，我们会发现真正起作用的就是malloc的n+1个变量很起作用，所以空间复杂度就是O（N）
实例3
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
递归函数在向下递归的时候创建函数栈帧，向上回归的时候回归内存，我们所要记录的空间复杂度是是累计创建的函数的个数，本函数是N-2个，所以空间复杂度是O（N）
9.20 有结果
10.6 行动，有束缚
10.20 与女性成员有斗争
11.4 考验亲密关系，新的方法
12.4 新的经历，冒险
12.25 大变
真正起作用的就是malloc的n+1个变量很起作用，所以空间复杂度就是O（N）
实例3
long long Factorial(size_t N)
{
return N < 2 ? N : Factorial(N-1)*N;
}
递归函数在向下递归的时候创建函数栈帧，向上回归的时候回归内存，我们所要记录的空间复杂度是是累计创建的函数的个数，本函数是N-2个，所以空间复杂度是O（N）
|