美文网首页
第一章 算法基础——算法性能分析

第一章 算法基础——算法性能分析

作者: 文颜 | 来源:发表于2019-10-13 12:45 被阅读0次

1.2 算法性能分析

算法复杂度是算法性能最基本的评价标准,由时间复杂度和空间复杂度组成,属于计算复杂性理论中的内容。复杂度是一个算法的时间运行函数,常用大写“O”表示。

(1)时间复杂度:描述算法的运行时间。

(2)空间复杂度:是指一个算法在运行过程中临时占有的存储空间大小,是算法需要的额外资源的体系。

算法的复杂度大约由6种,以时间复杂度为例:

1、O(1):表示常数级别完成问题的解,如在数组中获取索引为k的值。

2、O(lgn):一般采用分治法思想的算法,根据一定的解题特征对问题求解。

3、O(n):可以理解为将问题的数据进行了常数次迭代,如查找无序数组中的最大值。

4、O(nlgn):在数据的遍历过程中又采用的分支法的思想,如归并排序、快速排序。

5、O(n^2):表示对问题的数据进行了两次嵌套式迭代,如插入排序。

6、O(n^3):表示对问题的数据进行了三次嵌套迭代。

除上述常见的复杂度外,还有一些算法的复杂度比较高,需要用指数、阶乘等方式表示。在遇到不同级别的复杂度合并是,取复杂度最高的即可。

在现实中,时间复杂度和空间复杂度是互斥的。相同功能的算法中,优秀的算法总是在时间复杂度和空间复杂度中使得二者得值均尽可能小。

相关文章

  • 第一章 算法基础——算法性能分析

    1.2 算法性能分析 算法复杂度是算法性能最基本的评价标准,由时间复杂度和空间复杂度组成,属于计算复杂性理论中的内...

  • 给我巨大影响的技术书籍

    算法《算法概论》《算法设计与分析基础》 Anany Levitin《算法引论》Udi Manber《算法导论》《什...

  • 算法导论学习笔记(1)

    《算法导论》一共包含两部分,即算法分析和算法设计。 什么是算法分析? “算法分析是关于计算机程序性能和资源利用的理...

  • 查找汇总

    查找和排序是最基础也是最重要的两类算法,熟练地掌握这两类算法,并能对这些算法的性能进行分析很重要,这两类算法中主要...

  • 算法导论公开课笔记(一)算法分析与设计

    算法分析 算法分析是关于计算机程序性能和资源利用的理论研究;性能研究主要是学习如何让算法或者应用程序 运行的更快;...

  • 如何学习数据结构与算法

    算法学习经验 推荐: 入门: 数据结构启蒙:《数据结构与算法分析——C 语言描述》 算法启蒙:《算法设计与分析基础...

  • Day2 Chapter5.4

    5.4 估计、偏差、方差(衡量学习算法的性能,通过分析影响性能的因素从而提高学习算法的性能) 1. 点估计: 作用...

  • 如何分析一个排序算法?

    1.学习排序算法的思路?明确原理、掌握实现以及分析性能。2.如何分析排序算法性能?从执行效率、内存消耗以及稳定性3...

  • 第1章 算法简介

    第一章 算法简介 学习目标 为学习本书剩余章节打下坚实的基础; 编写二分搜索算法的代码; 学会使用大O​记号来分析...

  • 算法性能分析

    对于数据结构的基本概念我们不做叙述,本节重点讨论算法效率的度量。 性能分析的角度 一般我们从时间复杂度和空间复杂度...

网友评论

      本文标题:第一章 算法基础——算法性能分析

      本文链接:https://www.haomeiwen.com/subject/kdmhmctx.html