C语言算法的定义及分析详解

算法的定义

算法是一系列良定义的计算步骤

算法和程序的区别
算法

算法是指解决问题的一种方法或一个过程。

算法是若干指令的有穷序列,满足性质:

  1. 输入:有外部提供的量作为算法的输入。
  2. 输出:算法产生至少一个量作为输出。
  3. 确定性:组成算法的每条指令是清晰,无歧义的。
  4. 有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的。
程序
  1. 程序是算法用某种程序设计语言的具体实现。
  2. 程序可以不满足算法的性质(4)。
  3. 例如操作系统,是一个在无限循环中执行的程序,因而不是一个算法。
  4. 操作系统的各种任务可看成是单独的问题,每一个问题由操作系统中的一个子程序通过特定的算法来实现。该子程序得到输出结果后便终止。
算法的性质

有穷性:算法必须在有限步骤后终止

确定性:算法必须是没有歧义的

可行性:可以机械的一步步执行

算法的表示

自然语言、编程语言、伪代码

算法的分析
分析原则
  1. 统一机器性能
  2. 情况最坏分析

算法运行时间仅依赖于输入规模n,表示为T(n)

渐进分析
渐进记号

14B26EF5-8777-4B0A-43DA-DCA0120D749D.png

2C8EA97B-6B80-BEDD-65A2-D528B2A46101.png

37D97D1C-99D1-07E9-8F6E-F1D3755BB021.png

常用的复杂性函数

E088AF59-531A-D316-027F-D680D22D1DCE.png

01667258-87F2-98E6-84A6-6796ED26AF64.png

算法分析基本法则

非递归算法:

  1. for / while 循环

    循环体内计算时间循环次数;

  2. 嵌套循环

    循环体内计算时间*所有循环次数;

  3. 顺序语句

    各语句计算时间相加;

  4. if-else语句

    if语句计算时间和else语句计算时间的较大者。

收藏 (0)
评论列表
正在载入评论列表...
我是有底线的
为您推荐
    暂时没有数据