数据结构——算法和算法效率的度量

一、引言

二、算法

1 算法的基本概念

2 算法的复杂度

2.1 时间复杂度

2.1.1 概念

2.1.2 大O的渐进表示

3 算法的空间复杂度

3.1 概念

3.2 实例

4 实例分析

5 结论

一、引言

大家在写代码的时候有没有发现写同样功能的代码有多种不同的写法，而不同的代码也会给我们的程序带去不同的影响，比如有的代码执行的快，有的代码执行的慢；有的代码申请的空间大，有的代码申请的空间小，那这是为什么呢？因为是算法不同呀，那为什么不同呢，接下来就由姜糖给大家讲讲算法这一特殊的名词。

二、算法

1 算法的基本概念

算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，其中的每条指令表示一个或多个操作。此外，一个算法还具有下列五个重要特性：

有穷性。一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。
确定性。算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
输入。一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。
输出。一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

通常，设计一个“好”的算法应考虑达到以下目标：

正确性。算法应能够正确地解决求解问题。
可读性。算法应具有良好的可读性，以帮助人们理解。
健壮性。算法能对输入的非法数据做出反应或处理，而不会产生莫名其妙的输出。
高效率与低存储量需求。效率是指算法执行的时间，存储量需求是指算法执行过程中所需要的最大存储空间，这两者都与问题的规模有关。

2 算法的复杂度

算法效率的度量是通过时间复杂度和空间复杂度来描述的。

2.1 时间复杂度

说起时间可能有的人就会说，运行时间嘛我也会，把代码放在电脑上面跑一下就知道了。那大家想过没，我拿学校机房大LOL都卡的电脑和家里豪华rog全家桶来跑一个代码，他们的运行时间会一样吗？那有的人可能会说那放在同一台电脑上跑不就行了吗？那万一网卡了呢，时间不就又不一样了。所以算法中就有一个时间复杂度的概念。

2.1.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);
}

次数：

$F(N)=N^{2}+2*N+10$

当我们发现当N足够大时，2*N+10对函数的影响可以忽略不记，所以 $F(N)=N^{2}$ 。

所有我们计算时间复杂度的时候，我们其实并不一定有计算精确的次数，只需要一个大概就好了，所有我们这里可以用大O的渐进表示法。

2.1.2 大O的渐进表示

大O符号：是用于描述函数渐进行为的数学符号。

推导大O阶的方法：

用常数1取代运行时间中的所有加法常数。
在修改后的运行次数函数中，只保留高阶项。
如果最高阶项存在且不是1，且去除于这个项目相乘的常数。得到的结果就是大O阶。

所以上面例子代码的时间复杂度为：

$O(N^{2})$

*时间复杂度中，变量一般用N表示。

接下来再举一个让我们对大O阶渐进表示有更深一步的认识：

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);
}

那么这个函数的时间复杂度为什么呢？

F(N)=2N+10，只保留最高项，然后去掉最高项的常数，所以最后为O（N）。

在大O渐进表示中有一些特殊的：

比如有两个变量N和M，在没有特殊说明N或者M远远大于另外一个时：O(N+M);
O(常数)时用O(1)表示

接下来我们再来举一个例子：

const char strchr( const char* str, int character)
{
    while(*str)
    {
        if(*str==character)
            return str;

    ++str;
    }
}

这是一个在字符串中查找的函数

他的次数不固定，最好的情况为 O(1)，最坏的情况是O(n)，平均情况是O(n/2)。那我们该选择哪种情况呢？

这算法中我们一般选择最坏的运行情况，以保证算法的运行时间不会比它更长。

就如同我们生活中约会一样，我们到达的时间不可能比对象晚，不然后果很严重，所以我们要把最坏的时间告诉她，给我们留下充足的时间赴约。

3 算法的空间复杂度

3.1 概念

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

3.2 实例

下面我们来看代码进行分析：

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

该函数为阶乘递归，自身的递归每进行一次都会重新创造一个变量N,如图：

所以该函数创造的变量为N+1，用大O渐进法空间复杂度为O(N)。

4 实例分析

我们现在学习了空间复杂度和时间复杂度，那接下来我们用一道题结束今天的文章：

斐波那契数列（递归方法）：

#include<stdio.h>

int Fibonacci(int N)
{
	if (N < 3)
	{
		return 1;
	}
	else
		return Fibonacci(N - 1) + Fibonacci(N - 2);
}



int main()
{
	printf("%d", Fibonacci(10));
	return 0;
}

大家想想它的时间和空间复杂度为多少呢？

在分析之前我想告诉大家的是，做这类题的时候我们画图是很有利于我们理解的，如图：