算法的效率
效率是速度和空间消耗的度量。集中考虑程序的速度,也称运行时间或执行时间,用复杂度的阶(O)这一标准来衡量。空间的消耗或需求也可以用大O表示,而且它总是小于或等于时间需求。
以下是我的学习笔记:
1.求值与霍纳法则,即为秦九韶公式。
2.测定运行时间的最可靠方法是计数对运行时间有贡献的基本操作的执行次数。运行时间与这个计数成正比。
3.在分析程序的运行时间时,重要的是把程序看成算法,即独立于实现它的程序设计语言的一系列步骤。
4.一般地,算法是由多个基本操作组成的。有时我们计数所有的基本操作,而有时计数一个主导操作。
5.需要在算法的运行时间与它所操作的输入的规模之间建立关系。
6.需要观察不同的输入规模下的运行状况。特别需要作为输入规模的函数的比较次数。
7.在分析一个算法的运行时间时,重要的是把基本操作的数量与输入规模关联起来,即基本操作的数量必须表示成输入规模的函数。
8.函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,说f(n)的增长渐近快于g(n)。
9.大O:给定两个函数f(n)和g(n),f(n)=O(g(n))当且仅当存在一个常数c使得c*g(n)的增长渐近快于f(n)。
10.常数阶O(1):表示运行时间与输入规模无关。实例:访问数组中第i项的操作的运行时间
11.线性阶O(n):实例:在有n个值的数组中寻求最大(或最小)值的算法。
12.二次阶:实例:简单的多项式求值方案、选择排序算法。
13.对数阶(关于二叉搜索算法)、nlogn阶(某些排序算法)、三次阶。
14.指数阶:O(k^n),其中k是某个与输入规模n无关的常数,一般在解决特殊问题中探索“所有可能选择”(应用穷举)的算法中最常遇到。实例:给定n个整数,我们希望知道是否存在这些整数的一个子集,使得这个子集中的整数之和等于另一个给定整数K。
15.如果x比y增长得慢,那么x超前于y,用“<”表示,有如下顺序:1<logn<n^(1/2)<nlogn<n^(3/2)<n^2<n^3<k^n。
16.阶函数中的变量:对于出现在算法输入规模中的每一个变量,算法的运行时间的阶函数中至多有一项包含该变量。
17.通常,运行时间从最好情况运行时间到平均情况运行时间,再到最坏情况运行时间不断升级。
18.通常,除非特别指定,运行时间就是最坏情况运行时间。
19.通常,使用“时间复杂度”指运行时间需求,并使用“空间复杂度”指空间需求。当不用限定词地使用“复杂度”时,他们通常指时间复杂度。另外,如果他们没有特指平均情况或最坏情况,一般指的是最坏情况。
20.一个算法的空间需求总是小于或等于它的时间需求。
相关推荐
分析和计算算法效率的便捷方法 (杨朝霞兰州交通大学数理与软件工程学院,甘肃兰州 730070) : 摘 要: 通过对典型算法时间效率特征的分析,将求解算法时间复杂度的复杂过程进行简化,提出按算法的不同结构特性,具体问题...
各种排序算法效率分析比较及源代码 C语言实现 各种排序包括: 直接插入排序,折半插入排序,2—路插入排序和表插入排序;希尔排序和链式基数排序;起泡排序,快速排序,归并排序;简单选择排序,树形选择排序和堆...
第四课:算法效率的度量和存储空间需求 第五课:线性表的类型定义 第六课:线性表的顺序表示和实现 第七课:实验一 线性表的顺序存储实验 第八课:线性表的链式表示与实现 第九课:循环链表与双向链表 第十课...
数据结构的选择与算法效率 利用线段树解决picture问题解决,很经典
《算法效率与数据结构的选择》很详细地讲述了如何使用数据结构的选择使算法效率提高(里面有很多极精妙的技巧)
各种内部排序算法的时间复杂度分析结果只给出了算法执行的时间的阶,或大概执行时间。设计和实现内部排序算法效率比较平台,通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观的感受。
包含C、C++所有的函数名称,介绍算法效率与程序优化
要求完成在正序、逆序、小规模数据量(10、30、50)和大规模数据量(100、1000、10000等)情况下以移动次数和比较次数来分析算法效率。 几种内部排序算法在进行时间复杂度分析的时候给出了算法执行的大概执行时间。...
本文档为数据结构课程设计:搜索算法效率比较。内容比较完整!
数据结构的选择 线性结构 树形结构 的算法讲解和题型分析
老师的课件,比较好懂容易,只花费1个资源分
搜索算法效率比较.pdf
算法设计与分析课件
内部排序算法效率比较: 直接排序 起泡排序 快速排序 简单选择排序 堆排序 希尔排序
本ppt共有70页,包括算法设计课程的绪论,涵盖该学科所有知识点;还包括算法效率分析。最后配有习题。
一个简单的算法效率对比,实验证明,快速排序的效率比冒泡的效率高出很多啊!
算法效率培训课程.pptx
数据结构课程设计 搜索算法效率比较 两江大学出版社
基于大数据处理的模式匹配算法效率分析.pdf