时间复杂度之大O表示法

2024-03-10 14:12

本文主要是介绍时间复杂度之大O表示法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、概念

O表示法:
设T( n)和 g( n)是正整数集到正实数集上的函数。
称T( n) = O( g( n)) ,当且仅当存在一个正常数 C n0,使得对任意
n n0,有T( n) ≤ C g( n)。
其中:n 是算法输入的规模,如数组的长度,图的顶点数等;
一个算法时间复杂性是O(g( n)),称其时间复杂性的阶为g( n);
大 O 符号定义了函数 T(n) 的一个 上限 ,算法 的运行 时间(基本运算
次数)至多是g(n)的一个常数倍。
即: T(n)的增长速度至多与
g(n)的增长速度一样快。

二、常见时间复杂度

在每秒处理1亿次左右基本操作的计算机上,可以处理的1s对应的数据量量级:

O(n):10^7到10^8之间

O(nlogn):10^5到10^6

O(n^2):10^3到10^4

O(n^3):10^2到10^3

O(2^n):20到30

O(n!):10到12

三、 常用性质

(1)常系数,低次项以及低阶可忽略

(2)对数底可忽略

根据换底公式:

即时间复杂度的阶与对数底无关

以任何数为底的,都可以是O(logn)

(3)对数常数次幂可忽略

四、常用结果

(1)调和级数——O(logn)

(2)级数

这篇关于时间复杂度之大O表示法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/794482

相关文章

服务器集群同步时间手记

1.时间服务器配置(必须root用户) (1)检查ntp是否安装 [root@node1 桌面]# rpm -qa|grep ntpntp-4.2.6p5-10.el6.centos.x86_64fontpackages-filesystem-1.41-1.1.el6.noarchntpdate-4.2.6p5-10.el6.centos.x86_64 (2)修改ntp配置文件 [r

MiniGPT-3D, 首个高效的3D点云大语言模型,仅需一张RTX3090显卡,训练一天时间,已开源

项目主页:https://tangyuan96.github.io/minigpt_3d_project_page/ 代码:https://github.com/TangYuan96/MiniGPT-3D 论文:https://arxiv.org/pdf/2405.01413 MiniGPT-3D在多个任务上取得了SoTA,被ACM MM2024接收,只拥有47.8M的可训练参数,在一张RTX

批处理以当前时间为文件名创建文件

批处理以当前时间为文件名创建文件 批处理创建空文件 有时候,需要创建以当前时间命名的文件,手动输入当然可以,但是有更省心的方法吗? 假设我是 windows 操作系统,打开命令行。 输入以下命令试试: echo %date:~0,4%_%date:~5,2%_%date:~8,2%_%time:~0,2%_%time:~3,2%_%time:~6,2% 输出类似: 2019_06

【MRI基础】TR 和 TE 时间概念

重复时间 (TR) 磁共振成像 (MRI) 中的 TR(重复时间,repetition time)是施加于同一切片的连续脉冲序列之间的时间间隔。具体而言,TR 是施加一个 RF(射频)脉冲与施加下一个 RF 脉冲之间的持续时间。TR 以毫秒 (ms) 为单位,主要控制后续脉冲之前的纵向弛豫程度(T1 弛豫),使其成为显著影响 MRI 中的图像对比度和信号特性的重要参数。 回声时间 (TE)

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划

O(n)时间内对[0..n^-1]之间的n个数排序

题目 如何在O(n)时间内,对0到n^2-1之间的n个整数进行排序 思路 把整数转换为n进制再排序,每个数有两位,每位的取值范围是[0..n-1],再进行基数排序 代码 #include <iostream>#include <cmath>using namespace std;int n, radix, length_A, digit = 2;void Print(int *A,

算法复杂度的简单介绍

算法复杂度是衡量算法执行效率和资源消耗的指标,通常分为时间复杂度和空间复杂度。时间复杂度评估算法执行所需时间随输入规模的变化,空间复杂度评估算法占用内存的增长情况。复杂度通常用大O符号来表示,它描述了最坏情况下的增长速率。 1. 时间复杂度 时间复杂度表示算法执行所需时间随输入规模 nnn 的变化关系。常见的时间复杂度如下(从快到慢): a. 常数时间:O(1) 不管输入大小如何,算法总是

LeetCode:3177. 求出最长好子序列 II 哈希表+动态规划实现n*k时间复杂度

3177. 求出最长好子序列 II 题目链接 题目描述 给你一个整数数组 nums 和一个非负整数k 。如果一个整数序列 seq 满足在下标范围 [0, seq.length - 2] 中 最多只有 k 个下标i满足 seq[i] != seq[i + 1] ,那么我们称这个整数序列为好序列。请你返回 nums中好子序列的最长长度。 实例1: 输入:nums = [1,2,1,1,3],

未雨绸缪:环保专包二级资质续期工程师招聘时间策略

对于环保企业而言,在二级资质续期前启动工程师招聘的时间规划至关重要。考虑到招聘流程的复杂性、企业内部需求的变化以及政策标准的更新,建议环保企业在二级资质续期前至少提前6至12个月启动工程师招聘工作。这个时间规划可以细化为以下几个阶段: 一、前期准备阶段(提前6-12个月) 政策与标准研究: 深入研究国家和地方关于环保二级资质续期的最新政策、法规和标准,了解对工程师的具体要求。评估政策变化可

用Python实现时间序列模型实战——Day 14: 向量自回归模型 (VAR) 与向量误差修正模型 (VECM)

一、学习内容 1. 向量自回归模型 (VAR) 的基本概念与应用 向量自回归模型 (VAR) 是多元时间序列分析中的一种模型,用于捕捉多个变量之间的相互依赖关系。与单变量自回归模型不同,VAR 模型将多个时间序列作为向量输入,同时对这些变量进行回归分析。 VAR 模型的一般形式为: 其中: ​ 是时间  的变量向量。 是常数向量。​ 是每个时间滞后的回归系数矩阵。​ 是误差项向量,假