002算法的描述和分析

2021年4月11日 3421点热度 0人点赞 0条评论
内容目录

学习要求

算法复杂度计算方法

算法时间复杂度和空间复杂度的分析方法。

算法的描述和分析

【1】

数据的运算通过算法(Algorithm)描述的

算法是数据结构课程的重要内容之一。

算法是任意一个良定义的计算过程,它以一个或多个值作为输入,并产生一个或多个值作为输出。因此,算法是一系列将输入转换为输出的计算步骤。

一般地,一个问题的输入实例是满足问题陈述中所给出的限制、为计算该问题的解答所需要的所有输入构成的。若一个算法对于每个输入实例均能终止并给出正确的结果,则称该算法是正确的。正确的算法解决了给定的计算问题。

当然,能够求解一个问题并正确解决的算法有很多种,究竟使用哪种方法来评价这些算法的好坏呢?一般主要考虑以下三点:

  • 执行算法所耗费的时间;
  • 执行算法所耗费的存储空间;
  • 算法应易于理解、易于编码、易于调试等。

在 “底层级语言” 中例如 C 、C+++ 容易做到前两点,但是难以做到第三点;C#、JAVA 这类虚拟机语言可以做到第一第三点,但是运行时较大,当然光论算法存储空间大小可能会很小;Python 、JS 这类弱语言语言,一般 “性能较差”;Rust 解决了 C、C++ 很多缺点,但是学习曲线长、难以理解和编码;貌似 Go 语言做到了这三者均衡,好像现在很多人正在学习 Go 语言(俺也一样)。

编程语言是实现算法的利器,然而哪种语言都很难做到十全十美,但是我们可以根据编程语言的特点,利用其特性取优化代码,实现高性能程序。

一个算法是由多条语句组成的,算法耗费的时间是每条语句的执行时间之和,在这个时间中:

  • 每条语句的执行时间是:该语句的执行次数和每次执行时间(平均)的乘积
  • 一个语句的执行次数称为频度(Frequencry Count)

在 C#、Java 中有大量的封装方法,在引入其它库的情况下很难确定执行了多少语句,C# 中有 Linq ,一个方法里面可能还嵌套调用了 N 个步骤。因此不太语言之间是很难对比执行了多少语句的。还有其它原因,在 C#、Java 中很难比较一个算法的性能,当然在高级语言中,并不只是排序之类的算法比较,例如比较某个反射算法的性能等,这个时候无法用语句的算法复杂度预测性能,这是可以使用 Benchmark 工具进行测试。

【2】

算法具有由规定的基本运算即运算顺序所构成的完整的解题步骤,算法具有以下特性:

1,有穷性

一个算法必须包装执行有限步骤后结束。

2,确定性

算法的每一个步骤必须有明确的意义。

3,输入

4,输出

5,可行性

【3】

接下来是如何表示算法。

一般地,我们将算法求解问题的输入量称为问题的规模,并且用一个整数表示。例如矩阵乘积问题的规模是矩阵的阶数。

前面提到语句的执行次数称为频度,该算法中所有语句的频度之和使用 T(n) 表示:

    for (int j = array.Length - 1; j > 0; j--)   // n-1
            {
                for (int i = 0; i < j; i++)          // n(n-1)
                {
                        var sap = array[i];          // n²
                        array[i] = array[i + 1];    //  n²
                        array[i + 1] = sap;         //  n²
                }
            }

在忽略一些细节(不准确)的情况下,我们大致计算得:

T(n) = 4n² + 1

当然,每个语句的执行速度都是不一样的,这里我们无法计算出时间消耗。但是可以衡量一个算法的复杂度。

时间复杂度 是表示一个算法的时间耗费,是一个关于计算求解问题规模 n 的函数

当问题的规模趋无穷大时(例如上面代码示例的 array 数组),我们把 T(n) 的数量级称为算法的渐进时间复杂度

当然我们可以直接得出 n² 这里数量级,因为 ² 是最大的阶数。但是严谨来看,需要一个求解过程,例如:

lim T(n)/n² = lim(4n²-1)/n² = 4
n->∞        n->∞ 

4n²/n² = 4,4
1/n² = m ,而 0< m < 1

因为除于 n² ,该式子能够得出一个不为 0 的常数,我们把这个数量级使用 O(n) 表示。

那么称 T(n) = O(n²) 为此算法的渐近时间复杂度。

但是这样计算,需要掐准每个细节的执行次数,很不方便,而且容易出错,于是可以将基础操作作为计算依据。代码中基本操作如下:

                        var sap = array[i];          // n²
                        array[i] = array[i + 1];    //  n²
                        array[i + 1] = sap;         //  n²

因此,可以直接算出是 T(n) = 3n²。

当问题规模较大时,渐近时间复杂度与时间复杂度无限接近,因此我们可以使用渐近时间复杂度来表示时间复杂度

当求解的问题与 n 无关时,则该算法的时间复杂度为常数阶。

如:

temp = i;
i = j;
j = temp;

T(n) = 3,则 T(n) = O(1)。

因此,其时间复杂度为 O(1)。(注意,O(1) 表示其渐近时间复杂度,而不能说是 1 )。

【4】

下面来一些计算示例。

void func(int n)
{
    int i, j, x = 0;
    for (i = 0; i < n; ++i) {
        for (j = i + 1; i < n; j++){
            ++x;
        }
    }
}

把 x 当作基础操作,x 计算次数是:f(n) = n * (n-1)/2

显然,T(n) = O(n²) 。

【5】

常见的时间复杂度按数量级递增排列依次为:常数 0(1)、对数阶 0(log2n)、线形阶 0(n)、线形对数阶 0(nlog2n)、
平方阶 0(n2)立方阶 0(n3)、k 次方阶 0(nk)、指数阶 0(2n)。

问题规模为 n 是,各种数量级的情况如下:

复杂度

图片来自[xiaoxue.tuxi.com.cn]但是此网站被挂马了,大家别进去。

关于对数的复杂度,可能有些不了解,举个代码例子:

int count = 1;
while(count < n )
    count = count * 2;

如果 n = ?,执行次数为 ?

n   次数
2   1
4   2
8   3
... ...

可知,n = 2^(次数),当 n 趋近于无穷大时,设次数为 m,在坐标轴上都有一点 n,求 m。

此时 根据对数的概念,可知 m = log2 n。

简单来说,如果计算时,有这种变化的情况,可以列一个函数公式或者列一个表替代一些简单的数字进去,发现规律,再使用数学符号表示。

痴者工良

高级程序员劝退师

文章评论