首页 » php教程 » 正文

数据结构与算法概述

引子

什么是数据结构?如果翻阅不同的教材,可以看到五花八门的描述。事实上,这个问题在计算机科学界至今没有标准的定义。

在计算机科学中,数据结构(英语:data structure)是计算机中存储、组织数据的方式(维基百科)

思考问题

书籍摆放

问题:如果你是书店的主人,该如何摆放你的书籍,才能让顾客最快捷的找到想要的书籍?

  • 方法1:随便放

放书非常方便,有新书直接插到空位。但是查找很不方便,如果没有这本书,需要翻遍整个书架

  • 方法2:按照书名的拼音字母顺序排放

新书插入需要给新书腾出空间,造成图书需要向后移动

  • 方法3:把书架分成几块区域,每块区域指定摆放某种类别的图书;在每种类别内,按照书名的拼音字母顺序排放

查找和插入工作量都减少很多,但是无法预估每种类别的图书会有多少,容易造成空间的浪费

数字打印

问题:写程序实现一个函数 PrintN,使得传入一个正整数为 N 的参数,能顺序打印从 1 到 N 的全部正整数

//版本一
function PrintN($n)
{
    for ($i=1; $i <= $n; $i++) { 
        echo "{$i}\n";
    }
}
//版本二
function PrintN($n)
{
    if ($n > 0) {
        PrintN($n-1);
        echo "{$n}\n";
    }
}

当输入 N 为 100、1000、10000…,N 变的越来越大时候,实现版本一和版本二有什么区别?(debug_backtrace)

一元多项式计算

问题:一元多项式的标准表达式可以写成:f(x) = $a_0$ + $a_1$x + … + $a_{n-1}$$x^{n-1}$ + $a_n$$x^n$。现给定一个多项式的阶数 n,并将全体系数 ${a_i}^n_{i=0}$ 存放在数组 a[] 里。请写程序计算这个多项式在给定点 x 处的值

function f($n, $a, $x)
{
    $p = $a[0];
    for ($i=1; $i <= $n; $i++) { 
        $p += $a[$i] * pow($x, $i);
    }
    return $p;
}
$x = 2; $n = 1;
$a = [];
for ($i=0; $i <= $n; $i++) { 
    $a[$i] = $i+1;
}
$fn = f($n, $a, $x);
echo $fn . "\n";

通过提公因式 x 减少乘法的运算次数,把多项式改写为:

版权声明:枫叶林(https://blog.maplemark.cn)原创内容,请勿非法转载!已委托相关维权机构!

f(x) = $a_0$ + x($a_1$ + x(…($a_{n-1}$ + x($a_n$))…))

function f2($n, $a, $x)
{
    $p = $a[$n];
    for ($i=$n; $i > 0 ; $i--) { 
        $p = $a[$i-1] + $x * $p;
    }
    return $p;
}

解决问题的效率

解决一个非常简单的问题,往往也有多种方法,且不同方法之间的效率可能相差甚远。解决问题方法的效率,跟数据的组织方式有关,跟空间的利用效率有关,也跟算法的巧妙程度有关。

数据结构

定义

  • 数据结构的定义,首先应该包含数据对象在计算机中的组织方式——这类似于图书的摆放方法。并且,数据对象必定与一系列加在数据对象上的操作相关联,就如我们在书架上摆放图书是为了能找得到想要的书,或者是插入一本新买的书。

  • 在讨论数据结构的时候,关心的是数据对象本身以及它们在计算机中的组织方式,还要关心与它们相关联的操作集,以及实现这些操作的最高效的算法。

  • 关于数据对象在计算机中的组织方式,包含两个概念:数据对象集的逻辑结构、数据对象集在计算机中的物理存储结构

抽象数据类型

  • 抽象数据类型(Abstract Data Type)是一种对”数据结构”的描述,这种描述是”抽象”的。数据类型描述内容:数据对象集、与数据集合相关联的操作集。

  • 抽象:描述数据类型的方法不依赖于具体实现,即数据对象集合操作集的描述与存放数据的机器无关、与数据存储的物理结构无关、与实现操作的算法和编程语言均无关。抽象是计算机求解问题的基本方式和重要手段,使得一种设计可以应用于多种场景。

算法

定义

算法(algorithm)自于9世纪波斯数学家,在数学上提出了算法这个概念。

算法是一个有限指令集,它接受一些输入(非必须),产生输出,并一定在有限步骤之后终止。

算法不是程序,算法比程序更抽象,强调表现做什么,忽略细节性怎么做。这样的好处是使整体思路清晰易懂,形成模块化的风格。

算法复杂度

衡量、比较算法的指标主要有以下两个:

  • 空间复杂度 S(n):根据算法写成的程序在执行时占用存储单元的长度
  • 时间复杂度 T(n):根据算法写成的程序在执行时耗时时间的长度

分析一般算法效率:

  • 最坏情况复杂度 $T_{worst}$(n)
  • 平均复杂度 $T_{avg}$(n)

《数据结构与算法概述》 原文链接:https://blog.maplemark.cn/2019/07/数据结构与算法概述.html