【数据结构】算法效率的度量方法

简介: 【数据结构】算法效率的度量方法

在上篇文章中我们提到了算法的设计要求中我们要尽量满足时间效率高和存储量低的需求.这里的时间效率大都指算法的执行时间.


而算法的执行时间需通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量.度量一个程序的执行时间通常有两种方法:事后统计方法事前分析估算方法.


🎏事后统计方法

这种方法主要是通过设计好的测试程序和数据,利用计算机计时器对不同算法编制的程序运行时间进行比较,从而确定算法效率的高低.


但这种方法存在一些缺陷:


  • 因为要依靠设计好的程序来测试,那么我们就必须依据算法事先编好程序,这通常需要花费大量的时间和精力,并且如果最后的测试结果表明这是个很糟糕的算法,那么之前的所有努力就都白费了.
  • 时间的比较依赖于计算机硬件和软件等环境因素,有时会掩盖算法本身的优劣.计算机的处理器,所用操作系统,编译器,运行框架等软件的不同,也可以影响它们的结果,就算是同一台机器,CPU使用率和内存占用情况不一样,也会造成细微的差异.
  • 算法的测试数据设计困难,并且程序的运行时间往往还与测试数据的规模有很大关系,效率高的算法在小的测试数据面前往往得不到体现.


基于上面的缺陷,我们常常采用另一种事前分析估算的方法:事前分析估算方法.


🎏事前分析估算方法

在计算机程序编制前,依据统计方法对算法进行估算.


一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素:

  1. 依据的算法选用的策略,方法.
  2. 问题的规模,如求100以内还是1000以内的素数.
  3. 编译产生的代码质量.
  4. 书写程序的语言,对于同一个算法,实现语言的级别越高,执行效率就越低.
  5. 机器执行指令的速度.


这五个因素中,第一条是算法好坏的根本,第三条要由软件来支持,第四条要看程序员的选择,第五条要看硬件性能.这表明使用绝对的时间单位衡量算法的效率是不合适的.


抛开这些与计算机硬件,软件有关的因素,一个程序的运行时间,依赖于算法的好坏和问题的输入规模.

我们拿高斯求和算法举个例子:


从1加到100,第一种算法:

int i=0;            /*执行1次*/
int sum=0;          /*执行1次*/
int n=100;          /*执行1次*/
for(i=1;i<=n;i++)   /*执行n+1次*/
{
    sum=sum+i;      /*执行n次*/
}
printf("%d",sum);   /*执行1次*/

第二种算法:

int i=0;            /*执行1次*/
int sum=0;          /*执行1次*/
int n=100;          /*执行1次*/
sum=(1+n)*n/2;      /*执行1次*/
printf("%d",sum);   /*执行1次*/


显然,第一种算法一共执行了1+1+1+(n+1)+n+1=2n+5次.而第二种算法一共执行了1+1+1+1+1=5次.

事实上这两种算法的前三条语句和最后一条语句是一样的,所以我们只需要关注中间那部分代码即可.我们把循环看作一个整体,忽略头尾循环判断的开销,那么这两个算法其实就是n次与1次的差距.这样一比,两种算法的好坏显而易见了.


通过这个例子我们可以看出,测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数.运行时间与这个计数成正比.


我们不关心编写程序所用的程序设计语言是什么,也不关心这些程序将跑在什么样的计算机中,我们只关心它所实现的算法.


这样,不计那些循环索引的递增和循环终止条件,变量声明,打印结果等操作,最终,在分析程序的运行时间时,最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤.


我们在分析一个算法的运行时间时,重要的是把基本操作的数量与输入规模关联起来,即基本操作的数量必须表示成输入规模的函数.



如上面那个例子,同样的问题输入规模是n,第一种算法需要一段代码运行n次.那么这个问题的输入规模使得操作数量是f(n)=n.而第二种,无论n为多少,运行次数都为1,即f(n)=1.


可以看到,随着n值的越来越大,它们在时间效率上的差异也就越来越大了.



🎏函数的渐进式增长

函数的渐近增长:给定两个函数f(n)和g(n),如果存在一个整数N,使得对于所有的n>N,f(n)总是比g(n)大,那么,我们说f(n)的增长渐近快于g(n).


我们来看一个例子:算法A是n^2,

算法B是2n^2,

算法C是3n+1,

算法D是2n^2+3n+1.

次数 算法A(n^2) 算法B(2n^2) 算法C(3n+1)

算法D(2n^2+3n+1)

n=1 1 2 4 6

n=2

4 8 7 15
n=5 25 50 16 66
n=10 100 200 31 231
n=100 10,000 20,000 301 20,301
n=1,000 1,000,000 2,000,000 3,001 2,003,001
n=10,000 100,000,000 200,000,000 30,001 200,030,001
n=100,000 10,000,000,000 20,000,000,000 300,001 20,000,300,001
n=1,000,000 1,000,000,000,000 2,000,000,000,000 3,000,001 200,000,3000,001

显示详细信息

通过这组表格对比我们可以发现,随着n的增大,算法中的加减常数对结果的影响几乎可以忽略不计

,而非最高次像外的其他次要项对结果的影响也几乎可以忽略,以及最高项前的系数对结果的影响也可以忽略.


因此,判断一个算法的效率时,函数中的常数项和其他次要项以及最高项的系数常常可以忽略,而更应该关注主项(最高阶项)的阶数.



结语

当我们搞清楚算法效率的两种度量方法后,在数据结构算法篇,我们还将一起学习算法的时间复杂度算法的空间复杂度相关的知识.希望这些内容能对大家有所帮助,一起学习,一起进步!



数据结构算法篇思维导图:


相关文章
|
2月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
49 1
|
2月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
56 0
|
5月前
|
机器学习/深度学习 存储 算法
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
本文系统讲解从基本强化学习方法到高级技术(如PPO、A3C、PlaNet等)的实现原理与编码过程,旨在通过理论结合代码的方式,构建对强化学习算法的全面理解。
422 10
18个常用的强化学习算法整理:从基础方法到高级模型的理论技术与代码实现
|
6月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
153 10
 算法系列之数据结构-二叉树
|
6月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
140 3
 算法系列之数据结构-Huffman树
|
6月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
148 22
|
7月前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
176 30
|
8天前
|
机器学习/深度学习 算法 新能源
【优化调度】基于matlab粒子群算法求解水火电经济调度优化问题研究(Matlab代码实现)
【优化调度】基于matlab粒子群算法求解水火电经济调度优化问题研究(Matlab代码实现)
|
9天前
|
算法 机器人 定位技术
基于机器视觉和Dijkstra算法的平面建筑群地图路线规划matlab仿真
本程序基于机器视觉与Dijkstra算法,实现平面建筑群地图的路径规划。通过MATLAB 2022A读取地图图像,识别障碍物并进行路径搜索,支持鼠标选择起点与终点,最终显示最优路径及长度,适用于智能导航与机器人路径规划场景。
|
10天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于PSO粒子群优化的XGBoost时间序列预测算法matlab仿真
本程序基于Matlab 2024b实现,结合粒子群优化(PSO)与XGBoost算法,用于时间序列预测。通过PSO优化XGBoost超参数,提升预测精度。程序包含完整注释与操作视频,运行后生成预测效果图及性能评估指标RMSE。

热门文章

最新文章