数据结构算法之——时间复杂度和空间复杂度_阶乘 时间复杂度 递归树

目录

     一.数据结构与算法定义

         1. 大家首先先来了解一下什么是数据结构：

        2.其次是算法的介绍：

二.算法效率

1.算法效率定义：

三.时间复杂度

1.时间复杂度——相当重要！

2.练习：

练习1：计算一下Func1函数的基本操作执行了多少次？

练习2：

练习3：

练习4： 

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

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

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

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

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

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

        例3：二分查找

4.常见的复杂度如下：

四. 空间复杂度

1.定义：

2.练习：

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

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

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

---

     一.数据结构与算法定义

         1. 大家首先先来了解一下什么是数据结构：

        数据结构是计算机存储，组织数据的方式。指相互之间存在一种或多种特定关系的数据元素集合。数据结构是在内存中管理数据，对数据进行增删改查等多种步骤实现方式。

        2.其次是算法的介绍：

        算法就是定义良好的计算过程，它取一个或一组的值为输入，并产生一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。

        

二.算法效率

1.算法效率定义：

        算法效率分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称为空间复杂度。时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

三.时间复杂度

1.时间复杂度——相当重要！

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

2.练习：

练习1：计算一下Func1函数的基本操作执行了多少次？

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;
	}
	return count;
}

        如上图代码所示：这道题是求count++共执行了多少次？在最上面的嵌套循环中，外层for每执行一次循环，里层for 就要执行一圈。根据这个定义，我们可以知道count++共执行了n^2次；在中间这个for中根据判断条件可以知道，count++执行了2*n次；最后一个while循环中，M=10，每循环一次M--，直到M=0停止，所以count++执行了10次。

总的计算下来F(n)=n^2+2*n+10 

 那我们先来代入几个值进去：

N = 10时             F(N) = 130
N = 100 时          F(N) = 10210
N = 1000 时        F(N) = 1002010

        但在实际情况中，我们计算时间复杂度时，其实并不一定要计算精确的执行次数，而只需要大概执行次数，精确的计算很复杂费事，所以往往不那么重要！

---

        那么这里我们使用大O的渐进表示法。 大O符号（Big O notation）：

        是用于描述函数渐进行为的数学符号。 推导大O阶方法：

1、用常数1取代运行时间中的所有加法常数。

2、在修改后的运行次数函数中，只保留最高阶项。

3、如果最高阶项系数存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。

        这种方法十分方便我们计算，只保留了对算法影响最大的那一项核心，其余影响不大的的全部省去 （取其精华，去其糟粕！！！）

---

        再回到Func1中，它时间复杂度为：F(n)=n^2+2*n+10 ，使用大O的渐进表示法第二条规则：只保留最高项。Func1的时间复杂变为：F(n)=n^2（O(n^2) ），剩下的2*n+10都被省略。

        代入几个值进行对比：

 N = 10          F(N) = 100 ；

N = 100         F(N) = 10000 ；

N = 1000        F(N) = 1000000

        通过上图的对比我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，得出的结果也相差不多，简洁明了的表示出了大致的执行次数。 

        N越大，后两项对结果的影响就越小。

---

练习2：

// 计算Func2的时间复杂度？
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);
}

通过上述代码可知：第一个for循环中执行此数为2*n;第二个while循环中执行次数为10次。总的来说jfunc2精确的时间复杂度为：F(n)=2*n+10 。使用渐进表示法第二条，改为F(n)=2*n，其次再根据第三条规则：如果最高阶项系数存在且不是1，则去除与这个项目相乘的常数。因为F(n)的系数为2，则换为1，改为F(n)=N（O(n) )

---

练习3：

// 计算Func3的时间复杂度？
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;
}
printf("%d\n", count);
}

        如上图所示：这两次for循环都是独立的，且循环次数也不同，精确的时间复杂度为：F(n)=m+n 。根据渐进表示法第二条规则只保留最高项，但m与n都是级别相同，所以具体情况具体分析：

 若m>n，则F(n)=m            (省略n)

  若m<n，则F(n)=n             (省略m)

若m=n，则F(n)=m或F(n)=n        

---

练习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)。

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

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