数据结构算法之——时间复杂度和空间复杂度

练习4： 

// 计算Func4的时间复杂度？
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
 ++count;
}
printf("%d\n", count);
}

        这次的Fun4的总执行次数为100次，F(n)=100。根据渐进表示法第一条规则： 用常数1取代运行时间中的所有加法常数。 所以F(n)=1 （O(1) ）

练习5：冒泡排序的时间复杂度

// 计算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个无序元素第一次循环进行n-1次比较，第二次循环进行n-2次，直到最后一次循环执行1次比较 ）：a(n)=n-1，n-2，......，3，2，1。

所以它的时间复杂度就是等差数列的前N项和公式结果：

                                使用渐进表示法第二三条规则后，F(n)=n^2 

练习6：计算n的阶乘的时间复杂度：

long long Factorial(size_t N)
{
    if(N<2){
    return N;
    }
     return Factorial(N-1)*N;
}

上图代码对于计算n的阶乘，使用的是递归算法，每次递归的过程：

F(N)——>F(N-1)——>F(N-2)——>............——>F(2)——>F(1) 

每次递归的时间复杂度为O(1)，但递归的总次数为N次，所以 N*O(1)=O(N)，所以n的阶乘的递归算法时间复杂度为O(N)。

练习7：计算斐波那契数列递归的时间复杂度

// 计算斐波那契递归Fibonacci的时间复杂度？
long long Fibonacci(size_t N)
{
        if(N<3){
            return N;
               }
    return Fibonacci(N-1)+Fibonacci(N-2);
}

对于斐波那契数列的递归算法共调用了2^N次：

        这是一个经典的等比数列：2^0，2^1，2^2，2^3，.....，2^(n-1)，共n个数 ，每两个数之间都是2倍关系，而递归算法的时间复杂度则是等比数列的前n项和结果：

        使用渐进表示法后，1省略了，F(n)=2^n 

 3.时间复杂度的好坏情况：

        另外有些算法的时间复杂度存在最好、平均和最坏情况：

          最坏情况：任意输入规模的最大运行次数(上界)

          平均情况：任意输入规模的期望运行次数

          最好情况：任意输入规模的最小运行次数(下界)

        例1：实现在字符串中查找某个字符的算法，

        假如字符串中的字符有n个。最好情况是查找一次或者两次就成功找到，即复杂度为：O(1)；最坏情况是从头到尾查找到最后一个字符才找到或者查找了整个字符串也没找到，即复杂度为：O(N)；平均情况是查找了二分之N次才找到， 即复杂度为：O(N/2)。

        例2：在上边做过的冒泡排序中：

最好的情况：数组本身是顺序的，外层循环遍历一次就完成：O(n)

                           最坏的情况：数组本身是逆序的，内外层遍历就完成：O(n2)

        例3：二分查找

// 计算二分查找的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
assert(a);
int begin = 0;
int end = n-1;
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(1)。

最坏情况：即使找到最后了也没有找到该元素，为O(log2(N) )。为什么二分查找最坏的时间复杂度是log以2为底的N？        

假设有N个元素，最坏的情况是查找了X次

N=2^X      则X=log2(N)

        做事往往要考虑最坏的打算，要悲观的保守估计，基于此种观念，我们在计算时间复杂度时，关注的是算法的最坏情况。

4.常见的时间复杂度如下：

四. 空间复杂度

1.定义：

        空间复杂度是对一个算法在运行过程中临时占用或额外开辟存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践 复杂度类似，也使用大O渐进表示法。空间复杂度只选取影响最大的那一项。

         相比较时间复杂度，空间复杂度与其最大的区别是：空间可以重复利用，不需要累计；时间是一去不复返，需要累计。

2.练习：

冒泡排序算法的空间复杂度：

// 计算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;
 }
}

        解析：如代码所示，函数接收了一个数组共创建了三个变量：exchange、end、i，总共开辟了三个空间，而形参是数组，它是作为条件在函数中，所以在函数栈帧中不会额外开辟空间。临时占用或额外开辟存储空间大小的量度 基于此，空间复杂度为O(1)。比如end变量，它在循环中虽然是被创建了n次 ，产生了n个 end变量，但它们所占用的是同一块空间。变量i和变量exchange 也是被创建了n次，但也是占用着各自相同的空间。空间是重复利用的！！！

练习2：n的阶乘空间复杂度

// 计算阶乘递归Factorial的空间复杂度？
 
long long Factorial(size_t N)
{
    if(num==0)
     return 1;
    Factorial(N-1)*N;
}

        这是递归算法，所以每次调用Factorial都会开辟空间，递归调用了N+1次，所以共开辟了N+1的空间，函数栈帧也就开辟了N+1个Fac栈帧，所以空间复杂度是F(n)=(N+1)，使用渐进表示法后变成：O(N) 

练习3：求斐波那契递归的空间复杂度 

// 计算斐波那契递归Fibonacci的空间复杂度？
long long Fibonacci(size_t N)
{
        if(N<3){
            return N;
               }
    return Fibonacci(N-1)+Fibonacci(N-2);
}

        对于斐波那契的时间复杂度来说是O(2^N) ，是因为函数递归调用时，时间是不可重复利用的，一去不复返，所以复杂度极高。

        而空间复杂度中，空间可以重复利用，F(N)会首先调用左边的F(N-1)，接着一直往下调用直到最底层F(1)，接着从下至上返回函数，直到F(N-1)空间返回F(N)时，被逐一销毁，但只是把使用过的空间使用权还给操作系统，当F(N)接着调用右边的F(N-2)时，系统为F(N-2）开辟的空间还是之前为F(N-1)开辟的空间，重复利用而已，基于此，函数的空间复杂度就会小很多很多，为O(N)。

        结论：申请空间就和租房一样，释放空间就和退房一样，空间可以重复利用。用户退了房子，房东拿回了房间使用权，还可以继续给下一个人租住。

        时间用完了就没了，不能借！！！