算法

算法(algorithm):是对特定问题求解步骤的一种描述,它是指令有限序列,其中每一条指令表示一个或多个操作。

算法的5个特性

(1)又穷性: 一个算法必须总是(对任何的合法输入值)在执行有穷步之后结束,且每一步都必须在有穷时间内完成。

(2)确定性:算法中每一条指令必须有确切的含义,读者理解时不会产生二义性。并且,在任何条件下,算法只是一条唯一的执行路径,即对相同的输入只能得到相同的输出。

(3)可行性算法是可以实现的,即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的

(4)输入:一个算法有零个或多个输入。

(5)输出:一个算法又一个或多个输出。

算法的设计要求

(1)正确性(correctness)

(2)可读性(readability)

(3)健壮性(robustness)

(4)效率与低存储量需求

算法效率的度量

1. 时间复杂度

  • n:问题的规模,例如求100以内还是1000以内的素数

  • 频度:某语句在算法中被执行的次数。

  • T(n):所有语句的频度之和,n为问题规模。

 

算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间复杂度记作:

                     T(n)=O(f(n))

它表示随着问题规模n的增大,算法的执行时间增长率和f(n)的增长率相同

时间复杂度的关系如下:

O(1) < O(log_2n) < O(n) < O(nlog_2n) < O(n^2) < O(n^3) < O(2^n)

时间复杂度函数对比(图片来自网络):

2. 空间复杂度

一个算法的空间复杂度是指该算法所耗费的存储空间,计算公式计作:S(n) = O(f(n))。其中 n 也为数据的规模,f(n) 在这里指的是 n 所占存储空间的函数。

常用的空间复杂度:

  • 空间复杂度 O(1)
  • 空间复杂度 O(n)
  • 空间复杂度 O(n^2)

文章参考:

《数据结构》(C语言版)[清华大学出版社]

 

最后修改于 2019-09-27 15:32:30
如果觉得我的文章对你有用,请随意赞赏
扫一扫支付
上一篇