欢迎您光临本小站。希望您在这里可以找到自己想要的信息。。。

数据结构与算法基础(下)

架构&设计模式 water 631℃ 0评论

算法及性能分析

算法设计是最具创造性的工作之一,人们解决任何问题的思想、方法和步骤实际上都可以认为是算法。人们解决问题的方法有好有坏,因此算法在性能上也就有高低之分。

算法

算法是指令的集合,是为了解决特定问题而规定的一系列操作。它是明确定义的可计算过程,以一个数据集合作为输入,并产生一个数据集合作为输出。算法通常来说具有一下五个特性:

输入:一个算法应以待解决的问题的信息作为输入

输出:输入对应指令集处理后得到的信息

可行性:算法是可行的,即算法中的每一条指令都是可以实现的,均能在有限的时间内完成

有穷性:指令执行的指令个数是有限的,每个指令在有限时间内完成,因此整个算法也是在有限时间内可以结束的

确定性:算法对于特定的合法输入,其对应的输出是唯一的。即当算法从一个特定输入开始,多次执行同一指令集结果总是相同的

简单的说,算法就是计算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,都是在实施某种算法。前者是算法的逻辑形式,后者是算法的代码形式

时间复杂性

在计算机资源中,最重要的就是时间与空间。评价一个算法性能的好坏,实际上就是评价算法的资源占用问题。

去掉表示算法运行时间中的低阶项和首项常数,就称我们是在度量算法的渐进时间复杂度,简称时间复杂度

空间复杂性

算法的空间复杂性同样是由算法运行时使用的空间来评价的。我们把算法使用的空间定义为:为了求解问题的实例而执行的操作所需要的存储空间的数目,但是它不包括用来存储输入实例的空间

算法时间复杂度分析

计算循环次数

分析最高频度的基本操作

最佳、最坏与平均情况分析

一般情况下,所有算法对于任何输入实例,它的时间复杂度都是相同的。但是有些算法的执行时间不但是规模的函数,也是输入实例数据元素初始顺序的实例

均摊分析

在均摊分析中,我们可以算出算法在整个执行过程中,或多次执行过程中所用时间的平均值,称为该算法的均摊运行时间。均摊分析保证了算法的平均代价,这与平均情况分析是不同的,在平均分析中必须知道每种输入实例的分布,计算所有不同输入实例才能得到平均值。

转载请注明:学时网 » 数据结构与算法基础(下)

喜欢 (0)or分享 (0)

您必须 登录 才能发表评论!