数据结构：时间复杂度和空间复杂度_数据结构

1.时间复杂度

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数（数学函数表达式），它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有把程序放在机器上运行起来，才能知道。但这就需要把每个算法都进行上机测试，这很麻烦，所有才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

(1)我们给出下列例子来计算时间复杂度：

可以得出f(n) = n*n + 2*n + 10；当n越大时，n的最高次项对结果的影响最大。

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大o的渐进表示法。所以我们用o(n^2)来表示func1的时间复杂度。

大o的渐进表示法：
大o符号是用于描述函数渐进行为的数学符号。
推导大o阶方法： 1.用常数1取代运行时间中的所有加法常数。
2.在修改后的运行次数函数中，只保留最高阶项。
3 如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大o阶。

(2)变量与常数

(3)两个变量

(4)当一个算法要求被优化到时间复杂度为o(1)，即代表优化到常数次。

（5）当一个算法随着输入不同，时间复杂度不同，时间复杂度做悲观预期，看最坏的情况。

const char* strchr(const char* str, int character)
{//strchr:库函数,在str中查找character
	//...
	while(*str)
	{
		if (*str == character)
		return str;
		else
			++str;
	}
}

（6）冒泡排序的时间复杂度，取最坏情况

(7)二分查找的时间复杂度，取最坏情况
二分查找是有序的，最好的情况是在第一次就查找成功，最坏的情况是在begin不再小于end即没有找到这个数，此时每次折半已经循环了log2(n)次。

（8）递归算法时间复杂度：递归次数*递归被调用的次数

（9）斐波那契数列递归算法的时间复杂度

2.空间复杂度

空间复杂度也是一个数学函数表达式，是对一个算法在运行过程中临时额外占用存储空间大小的度量。空间复杂度不是程序占用了多少字节的空间，计算这个没有太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大o渐进表示法。
注意：函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时显式申请的额外空间来确定。

（1）冒泡排序的空间复杂度

在这个程序中，每次给 i 赋不同的值，但是 i 所占用的空间没有变，没有创建新的空间；同理可得，其它变量值（如：end)改变但空间占用不变，这些变量(占用空间)是整数个，所以空间复杂度是o(1)。

（2）斐波那契数列的空间复杂度

（3）阶乘递归fac的空间复杂度

（4）递归的斐波那契数列的空间复杂度:

先进行最左边一列计算，创建的空间可以被后续重复利用，栈空间依据递归的深度创建。

3.习题练习

. - 力扣（leetcode）

针对该题，有三种解法：
（1）用0~n的累加和减去整个数组的累加和得到数组中缺失的值

int missingnumber(int* nums, int numssize){
    int sum = (numssize+1)*numssize/2;
    for(int i = 0;i<numssize;i++)
    {
        sum -= nums[i];
    }
    return sum;
}

（2）再创建一个数组arr ，遍历nums数组，它是几就存储到对应arr下标的位置，遍历arr数组，下标与值不匹配的项就是缺失值。

（3）给定一个值x = 0；x先跟0~n的所有值异或，再跟数组中的每个值异或，最后x的值就是缺失值。（任何数与0异或都是本身，相同的数异或结果为0，这样就会找出只出现一次的缺失值）

int missingnumber(int* nums, int numssize){
   int x = 0;
   int i = 0;
   for(i=0;i<=numssize;i++)
   {
    x ^= i;
   }
   for(i=0;i<numssize;i++)
   {
    x ^= nums[i];
   }
   return x;
}

. - 力扣（leetcode）

void reverse(int* a,int left,int right)
{
    while(left<right)
    {
        int t=a[right];
        a[right]=a[left];
        a[left]=t;
        left++;
        right--;
    }
}
void rotate(int* nums, int numssize, int k) {
    if(k>=numssize)
    {k%=numssize;}
    reverse(nums,0,numssize-1-k);
    reverse(nums,numssize-k,numssize-1);
    reverse(nums,0,numssize-1);
}