数据结构与C

数据结构与C 知识量:8 - 24 - 99

1.2 算法及算法分析><

算法特性- 1.2.1 -

算法具有五个特性:

  1. 输入:算法具有零个或多个输入。

  2. 输出:算法至少具有一个或多个输出,包括打印输出,返回等。

  3. 有穷性:算法在执行有限的步骤之后,自动退出而不会出现无限的循环,并且每一个步骤都在可接受的时间内完成。

  4. 确定性:算法的每一个步骤都具有确定的含义,不会出现二义性。

  5. 可行性:算法的每一个步骤都是可行的,也就是说,每一个步骤都能通过执行有限的次数完成。

此外,算法设计还要求具有正确性、可读性、健壮性,并要求时间效率高和存储量低。

算法描述- 1.2.2 -

算法描述是对设计出的算法,用一种方式进行详细的描述,以便与人交流。算法可采用多种描述语言来描述,如自然语言、伪代码、程序流程图等。

在描述算法时,需要确保描述具有有穷性、确定性、可行性、有输入和有输出等特征。同时,还需要考虑算法的正确性、可读性、健壮性,并要求时间效率高和存储量低。

算法分析- 1.2.3 -

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。

在计算机科学中,算法要用计算机算法语言描述,算法代表用计算机解一类问题的精确、有效的方法。为了便于比较同一问题的不同算法,通常的做法是:从算法中选取一种对于所研究的问题来说基本运算的原操作,以该原操作重复执行的次数作为算法的时间度量。

算法分析的目标是要找出问题规模会怎么影响一个算法的执行时间。常见的大O数量级函数有O(1)、O(logn)、O(n)、O(nlogn)、O(n²)、O(n³)、O(2^n)、O(n!)等。