当前位置：首页 > news >正文

1、数据结构与算法(Python版-啃书)-绪论

news 2025/5/18 7:29:26

1.1 计算机问题求解

一般而言，人们需要的不是解决一个具体问题的程序，而是解决一类问题的程序。

对于求平方根这样的简单问题，人们希望的也不是专用于求某个数(例如2)的平方根的函数，而是能求任何数的平方根的函数。

用计算机解决问题的过程分为两个阶段:

1、程序开发者针对要解决的问题开发出相应的程序； ---- 程序设计

2、使用者运行程序处理问题的具体实例，完成具体计算。 ---- 功能使用

1.1.1 程序开发过程

1、需求分析阶段---模糊需求细化

2、设计阶段---严格描述求解过程

3、编码阶段 -- 使用编程语言写代码实现

4、检查测试阶段 --- 检查语法错误，修正逻辑错误

1.3、算法和算法分析

1.3.1、问题、问题实例和算法

算法性质：有穷性、可行性、确定性、终止性、输入/输出。

算法描述：问题解决的办法，要方便人们的阅读和使用。常见的算法：枚举法、贪心法、分治法、回溯法、动态规划、分值限界法等。

程序：算法的实现，算法的落地。

算法设计模式：是人们对经验的总结，只能借鉴，不应作为教条。这些模式并不相互隔绝也不互相排斥。例如，一般而言复杂的问题都需要分解;而最简单的情况经常可能采用枚举和判断的方式处理。

1.3.2、算法的代价及其度量

在研究现实世界中的计算问题时，必须考虑计算的代价。该算法:在求解过程中需要多少存储空间?完成问题实例的求解需要多长时间?

同一个算法能应用于不同的实例，计算的实际代价通常与实例的规模(大小)有关。3000X3000的矩阵计算自然要比3X3的矩阵计算花费更多的时间和空间。因此，可以把一个算法的计算(时间和空间)开销定义为问题的实例规模的函数。

算法分析就是针对一个具体算法，设法确定一种函数关系，以问题实例的某种规模n为参量，反映出这个算法在处理规模n的问题实例时需要付出的时间(或者空间)代价。

同一算法，在大规模集合操作中，比如在一个数组中查找某一个数据，可能很快就找到了，可能要耗费很长时间才能找到。因此，在有关算法的研究和分析中，人们主要关注算法的最坏情况代价，有时也关注算法的平均代价。

“大O记法"描述算法性质：

时间复杂度：T(n)=O(g(n))

空间复杂度：S(n)=O(g(n))

常用的复杂度函数：

O(1) ---- 常量复杂度

O(log n) --- 对数复杂度

O(n) ----- 线性复杂度

O(nlog n)

O(n^2) --- 平方复杂度

O(n^3) ---- 立方复杂度

O(2^n) ---- 指数复杂度

1.3.3、算法分析

0.基本操作，认为其时间复杂度为O(1)。如果是函数调用，应该将其时间复杂度代入，参与整体时间复杂度的计算。
1.加法规则（顺序复合)。如果算法（或所考虑算法片段)是两个部分(或多个部分)的顺序复合，其复杂性是这两部分(或多部分)的复杂性之和。以两个部分为例:
        T(n)=Ti(n)＋T(n)=O(T (n))+O(T2 (n))=O(max (T(n), T2 (n)))
其中T;(n)和T(n)分别为顺序复合的两个部分的时间复杂度。由于忽略了常量因子，加法等价于求最大值,取T(n)和 T2(n)中复杂度较高的一个。
2.乘法规则(循环结构)。如果算法（或所考虑的算法片段)是一个循环，循环体将执行T(n)次，每次执行需要T(n)时间，那么:
        T(n)一T(n)×T2(n)=O(T (n)×O(T(n))=O(T(n)×T2(n))
3.取最大规则(分支结构)。如果算法（或所考虑算法片段)是条件分支，两个分支的时间复杂性分别为T(n)和 T2(n)，则有:
        T(n)=O(max(T(n),T2(n)))