算法分析

算法的效率可以在执行之前和执行之后的两个不同阶段进行分析。 它们如以 -

  • 先验分析 - 这是一种算法的理论分析。通过假定所有其他因素(例如处理器速度)是恒定的并且对实现没有影响来测量算法的效率。
  • 后验分析 - 这是对算法的经验分析。 所选择的算法使用编程语言来实现。 然后在目标计算机上执行。 在此分析中,收集实际的统计数据,如运行时间和所需空间。

算法的复杂性

假设X是算法,n是输入数据的大小,算法X使用的时间和空间是决定X的效率的两个主要因素。

  • 时间因素 - 时间通过计算关键操作的数量来衡量,如排序算法中的比较。
  • 空间因素 - 空间通过计算算法所需的最大存储空间来测量。

算法f(n)的复杂性以算法n所需的运行时间和/或存储空间为输入数据的大小。

空间复杂性

算法的空间复杂度表示该算法在其生命周期中所需的存储空间量。 算法所需的空间等于以下两个组件的总和 -

  • 固定部分,是存储某些数据和变量所需的空间,与问题的大小无关。 例如,使用的简单变量和常量,程序大小等
  • 变量部分是变量所需的空间,其大小取决于问题的大小。 例如,动态内存分配,递归堆栈空间等。

任何算法P的空间复杂度S(P)S(P)= C + SP(I),其中C是固定部分,S(I)是算法的变量部分,取决于实例特征I,下面是一个简单的例子,试图解释这个概念 -

Algorithm: SUM(A, B)
Step 1 -  START
Step 2 -  C ← A + B + 10
Step 3 -  Stop

这里有三个变量ABC以及一个常量。 因此S(P)= 1 + 3。现在,空间取决于给定变量和常量类型的数据类型,并且它将相应地相乘。

时间复杂性

算法的时间复杂度表示算法运行完成所需的时间量。 时间要求可以定义为一个数值函数T(n),其中T(n)可以测量为步数,如果每步消耗的时间不变。

例如,添加两个n位整数需要n个步骤。 因此,总计算时间是T(n)= c * n,其中c是加两位所用的时间。 在这里,观察到T(n)随着输入尺寸的增加而线性增长。

移动端设备除iPad Pro外,其它移动设备仅能阅读基础的文本文字。
建议使用PC或笔记本电脑,浏览器使用Chrome或FireFox进行浏览,以开启左侧互动实验区来提升学习效率,推荐使用的分辨率为1920x1080或更高。
我们坚信最好的学习是参与其中这一理念,并致力成为中文互联网上体验更好的学练一体的IT技术学习交流平台。
您可加QQ群:575806994,一起学习交流技术,反馈网站使用中遇到问题。
内容、课程、广告等相关合作请扫描右侧二维码添加好友。

狐狸教程 Copyright 2021

进入全屏