科学知识:时间复杂度计算方法
作者:junjie 发布时间:2023-09-18 21:42:28
一、定义
(1)如果一个问题的规模是n,解这一问题的某一算法所需要的时间为T(n),它是n的某一函数 T(n)称为这一算法的“时间复杂性”。我们常用大O表示法表示时间复杂性,称之为大O记法。
(2)一个问题本身也有它的复杂性,如果某个算法的复杂性到达了这个问题复杂性的下界,那就称这样的算法是最佳算法。常见的时间复杂度高低顺序如下:
O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < O(2^n) < O(n!) < O(n^n)
二、时间复杂度计算步骤
⑴ 找出算法中的基本语句;
算法中执行次数最多的那条语句就是基本语句,通常是最内层循环的循环体。
⑵ 计算基本语句的执行次数的数量级;
只需计算基本语句执行次数的数量级,这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析,并且使注意力集中在最重要的一点上:增长率。
⑶ 用大Ο记号表示算法的时间性能。
将基本语句执行次数的数量级放入大Ο记号中。
如果算法中包含嵌套的循环,则基本语句通常是最内层的循环体,如果算法中包含并列的循环,则将并列循环的时间复杂度相加。
三、时间复杂度计算规则
(1)对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间
(2)对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"
求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))
特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))
(3)对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间
(4)对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"
乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1*T2=O(f(n)*g(n))
(5)对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度
猜你喜欢
- 前言图像分割是指根据灰度、色彩、空间纹理、几何形状等特征把图像划分成若干个互不相交的区域。最简单的图像分割就是将物体从背景中分割出来1.图像
- PL/SQL单行函数和组函数详解 函数是一种有零个或多个参数并且有一个返回值的程序。在SQL中Oracle内建了一系列函数,这些函数都可被称
- 前言大部分初学编程的人来说刚开始都会练习判断两个数或者三个数的大小,来熟悉某种语言的特性和最基本的if,else循环,当我们学习了更高级的语
- 前言字符串是 字符的序列 。字符串基本上就是一组单词。我几乎可以保证你在每个Python程序中都要用到字符串,所以请特别留心下面这部分的内容
- JavaScript 语法约定1、大小写的区分1). JavaScript的关键字,永远都是小写的;2). 内置对象,如Math和Date是
- 首先,我们来随便写一个带空格的列表:list1 = ['122','2333','3444'
- 前言最近学习了Fiddler抓包工具的简单使用,通过抓包,我们可以抓取到HTTP请求,并对其进行分析。现在我准备尝试着结合Python来模拟
- 前言Vue 原本有一个官方推荐的 ajax 插件 vue-resource,但是自从 Vue 更新到 2.0 之后,官方就不再更新 vue-
- 接触了Vue模块化开发才发现JavaScript组件化开发的演变一直在继续,以前也没有特别在意这一块内容,写着代码能调试运行不报错就可以了,
- 前言为了满足用户渠道推广分析和用户账号绑定等场景的需要,公众平台提供了生成带参数二维码的接口。使用该接口可以获得多个带不同场景值的二维码,用
- 可以,具体方法如下::<% set fs=createobject("scripting.
- 拼接字符串使用“+”运算符可完成对多个字符串的拼接,“+”运算符可以连接多个字符串并产生一个字符串对象。字符串不允许直接与其他类型数据拼接。
- 1.查询高于平均价格的商品名称: SELECT item_name FROM ebsp.product_market_price WHERE
- 列表更多的方法index():返回指定数据所在位置的下标 (注意:如果查找的数据不存在则报错。)。count():统计指定数据在当前列表中出
- make介绍借助Makefile我们在编译过程中不再需要每次手动输入编译的命令和编译的参数,可以极大简化项目编译过程。make是一个构建自动
- 如下所示:#提取目录下所有图片,更改尺寸后保存到另一目录from PIL import Imageimport os.pathimport
- Step1:确定操作系统Python 解释器的下载地址为:https://www.python.org/ ,点击&nbs
- 本文实例讲述了python元祖和字典的内建函数。分享给大家供大家参考,具体如下:元组Tuple元组是序列类型一种,也是不可变类型数据结构,对
- 写了个多层感知器,用bp梯度下降更新,拟合正弦曲线,效果凑合。# -*- coding: utf-8 -*-import numpy as
- 这里所谓的复杂表单,是指表单中包含多种不同的输入类型,比如下拉列表框、单行文本、多行文本、数值等。在经常需要更换这类表单的场合,需要有一个表