首页 > 编程语言 >算法中的大O记法

算法中的大O记法

时间:2024-08-15 10:26:56浏览次数:14  
标签:检索 记法 元素 算法 时间 n2 nlogn

目的
我们常需要描述特定算法相对于n(输入元素的个数)需要做的工作量。在一组未排序的数据中检索,所需的时间与n成正比;如果是对排序数据用二分检索,花费的时间正比于logn。排序时间可能正比于n2或者nlogn。我们需要有一种方式,用它能把这种说法弄得更精确,同时又能排除掉其中的一些具体细节,如C P U速度,编译系统(以及程序员)的质量等。我们希望能够比较算法的运行时间和空间要求,并使这种比较能与程序设计语言、编译系统、机器结构、处理器的速度及系统的负载等等复杂因素无关。
为了这个目的,人们提出了一种标准的记法,称为“大O记法”。在这种描述中使用的基本参数是n,即问题实例的规模,把复杂性或运行时间表达为n的函数。这里的“O”表示量级( order ),比如说“二分检索是O( logn)的”,也就是说它需要“通过l o gn量级的步骤去检索一
个规模为n的数组”。记法O ( f(n) )表示当n增大时,运行时间至多将以正比于f(n)的速度增长。O(n2)和O(nlogn)都是具体的例子。这种渐进估计对算法的理论分析和大致比较是非常有价值的,但在实践中细节也可能造成差异。例如,一个低附加代价的O(n2)算法在n较小的情况下可
能比一个高附加代价的O(nlogn)算法运行得更快。当然,随着n足够大以后,具有较慢上升函数的算法必然工作得更快。
我们还应该区分算法的最坏情况的行为和期望行为。要定义好“期望”的意义非常困难,因为它实际上还依赖于对可能出现的输入有什么假定。在另一方面,我们通常能够比较精确地了解最坏情况,虽然有时它会造成误解。前面讲过,快速排序的最坏情况运行时间是O(n2),但期望时间是O(nl o gn)。通过每次都仔细地选择基准值,我们有可能把平方情况(即O(n2)情况)的概率减小到几乎等于0。在实际中,精心实现的快速排序一般都能以(O(nlogn)时间运行。
下表是一些最重要的情况:

访问数组中的元素是常数时间操作,或说O( 1 )操作。一个算法如果能在每个步骤去掉一半数据元素,如二分检索,通常它就取O( l o gn)时间。用strcmp比较两个具有n个字符的串需要O(n)时间。常规的矩阵乘算法是O(n3),因为算出每个元素都需要将n对元素相乘并加到一起,所有元素的个数是n2。
指数时间算法通常来源于需要求出所有可能结果。例如, n个元素的集合共有2n个子集,所以要求出所有子集的算法将是O( 2n)的。指数算法一般说来是太昂贵了,除非n的值非常小,因为,在这里问题中增加一个元素就导致运行时间加倍。不幸的是,确实有许多问题(如著名的“巡回售货员问题” ),到目前为止找到的算法都是指数的。如果我们真的遇到这种情况,通常应该用寻找近似最佳结果的算法替代之。

标签:检索,记法,元素,算法,时间,n2,nlogn
From: https://blog.csdn.net/workflower/article/details/141158100

相关文章

  • 二分图最大匹配(匈牙利算法)
    二分图最大匹配(匈牙利算法)算法思路寻找增广路即一条以选中边开始,以选中边结束的路,它有一个重要的性质:选中边比未选中边多一.只需要不断贪心的找增广路,直到不存在为止具体实现以dfs(深度优先)为例1.从左部1号开始搜寻增广路2.令当前点编号为x遍历右部与x相连的点3.若当前......
  • NRBO-BP-Adaboost回归 基于牛顿拉夫逊算法优化BP神经网络-Adaboost多变量回归预测(多
    NRBO-BP-Adaboost回归基于牛顿拉夫逊算法优化BP神经网络-Adaboost多变量回归预测(多输入单输出)程序已经调试好,无需更改代码替换数据集即可运行!!!数据格式为excel!需要其他的都可以定制!1️⃣、运行环境要求MATLAB版本为2019b及其以上2️⃣、评价指标包括:R2、MAE、MSE、RPD、RMSE......
  • 冒泡排序算法
    C++实现冒泡排序算法:#include<iostream>usingnamespacestd;voidbubbleSort(intarr[],intn){for(inti=0;i<n-1;i++){for(intj=0;j<n-i-1;j++){if(arr[j]>arr[j+1]){//交换arr[j]和arr[j+1]inttemp=arr[j];arr[j]=arr[j+1];......
  • 【算法模板】计算几何:旋转卡壳求凸包直径
    旋转卡壳算法是一种几何算法,主要用于在二维平面上求解与凸包相关的最优问题。该算法利用凸包顶点的顺序性和对称性,通过模拟两个卡壳(calipers)沿着凸包边界的旋转来寻找最优解。常见的应用包括计算凸包的直径(即最远点对之间的距离)、最小包围矩形(最小面积矩形),以及最小宽度(宽度......
  • 操作系统-进程创建、同步与锁、通信、调度算法-学习笔记
    1.进程的基础概念1.1进程是什么?定义:进程是操作系统管理的一个程序实例。它包含程序代码及其当前活动的状态。每个进程有自己的内存地址空间,拥有独立的栈、堆、全局变量等。操作系统通过进程来分配资源(如CPU时间、内存等)并管理任务的执行。进程vs程序:程序:静态的代......
  • [插电式混合动力车辆][交替方向乘子法(ADMM)结合CVX]插电式混合动力车辆的能源管理:基于
     ......
  • 【优化交叉口的绿灯时间】基于遗传算法的交通灯管理研究(Matlab代码实现)
    ......
  • 子串查找算法KMP
    什么是子串查找        字符串子串查找是一种在较长的字符串(通常称为"主串"或"文本")中寻找一个较短字符串(称为"模式串"或"子串")的过程。这是计算机科学中的一个基本问题,在文本编辑、信息检索、生物信息学等多个领域都有广泛应用。主要的子串查找算法包括:暴力匹配法(B......
  • 卡尔曼滤波算法
    目录卡尔曼滤波基本原理卡尔曼滤波的数学模型卡尔曼滤波算法步骤1.初始化2.预测步骤3.更新步骤完整的卡尔曼滤波实现总结卡尔曼滤波是一种递归滤波器,广泛应用于信号处理和控制系统中,用于估计动态系统的状态。它通过结合预测和测量数据,在存在噪声的情况下对系统状......
  • sm2算法
    sm2算法简称国密,下面是百度讲解:SM2算法和RSA算法都是公钥密码算法,SM2算法是一种更先进安全的算法,在我们国家商用密码体系中被用来替换RSA算法。随着密码技术和计算机技术的发展,目前常用的1024位RSA算法面临严重的安全威胁,我们国家密码管理部门经过研究,决定采用SM2椭圆曲线算......