时间复杂度、空间复杂度,这里一次讲清楚

2024-06-12 16:36

本文主要是介绍时间复杂度、空间复杂度,这里一次讲清楚,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

无论是时间复杂度和空间复杂度都是是用来衡量算法在处理不同规模数据时所需的时间和内存的变化情况,是不同角度的衡量结果。

在算法分析中,大O符号(O)表示算法的渐近时间(或空间)复杂度。它描述了算法运行时间(或空间占用)与输入规模的增长关系。

结果

时间复杂度是衡量算法执行时间随着输入规模增长而增加的速率。以下是一些常见的时间复杂度,从低到高排列:

  1. O(1) - 常数时间复杂度

    • 算法的执行时间不随输入规模的变化而变化。
  2. O(log n) - 对数时间复杂度

    • 执行时间随输入规模的对数增长,常见于二分查找算法。
  3. O(n) - 线性时间复杂度

    • 执行时间与输入规模成正比,常见于简单遍历数组的算法。
  4. O(n log n) - 线性对数时间复杂度

    • 比线性时间复杂度稍慢,常见于高级排序算法如归并排序和快速排序的平均情况。
  5. O(n^2) - 二次时间复杂度

    • 执行时间与输入规模的平方成正比,常见于简单的双重嵌套循环,比如冒泡排序、插入排序的最坏情况。
  6. O(n^3) - 三次时间复杂度

    • 执行时间与输入规模的立方成正比,常见于三重嵌套循环。
  7. O(2^n) - 指数时间复杂度

    • 执行时间随着输入规模的指数增长,常见于解决递归问题的暴力解法,例如汉诺塔问题。
  8. O(n!) - 阶乘时间复杂度

    • 执行时间随着输入规模的阶乘增长,常见于计算全排列的暴力解法。

以下是一些更不常见但也有实际应用的时间复杂度:

  1. O(log^2 n)

    • 执行时间与输入规模的对数的平方成正比。
  2. O(n^c)

    • 多项式时间复杂度,其中 ( c ) 是一个常数。
  3. O(2^{O(n)}), O(2^{poly(n)})

    • 这些是更一般形式的指数时间复杂度,用来描述某些复杂算法的时间需求。
  4. O(n^n)

    • 一种极为复杂的时间复杂度,通常出现在极端情况下的组合问题中。

不同的时间复杂度代表了算法在处理大规模数据时的效率差异。选择合适的算法时,通常希望在满足需求的前提下,选用时间复杂度较低的算法。

空间复杂度同理

空间复杂度是指程序在运行过程中占用的内存空间与输入规模之间的关系。以下是一些常见的空间复杂度,从低到高排列:

  1. O(1) - 常数空间复杂度

    • 算法所需的空间不随输入规模的变化而变化。
  2. O(log n) - 对数空间复杂度

    • 所需空间随着输入规模的对数增长,常见于递归算法,如二分查找中的递归调用栈空间。
  3. O(n) - 线性空间复杂度

    • 所需空间与输入规模成正比,常见于需要额外数组或列表来存储数据的算法。
  4. O(n log n) - 线性对数空间复杂度

    • 所需空间比线性空间复杂度稍多,常见于某些高级排序算法,如基于递归实现的归并排序。
  5. O(n^2) - 二次空间复杂度

    • 所需空间与输入规模的平方成正比,常见于需要二维矩阵或表格存储数据的算法,如动态规划中求解最长公共子序列的问题。
  6. O(n^3) - 三次空间复杂度

    • 所需空间与输入规模的立方成正比,通常出现在需要三维数组的复杂问题中。
  7. O(2^n) - 指数空间复杂度

    • 所需空间随着输入规模的指数增长,常见于某些递归解决方案,如计算所有子集的暴力方法。
  8. O(n!) - 阶乘空间复杂度

    • 所需空间随着输入规模的阶乘增长,非常罕见,通常出现在计算全排列的暴力解法中。

以下是一些更不常见但也有实际应用的空间复杂度:

  1. O(n^c)

    • 多项式空间复杂度,其中 ( c ) 是一个常数,常见于一些复杂的数据结构或算法中。
  2. O(2^{O(n)}), O(2^{poly(n)})

    • 这些是更一般形式的指数空间复杂度,用来描述某些复杂算法所需的空间。
  3. O(n^n)

    • 一种极为复杂的空间复杂度,通常出现在极端情况下的组合问题中。

选择算法时,不仅要考虑时间复杂度,还要考虑空间复杂度,以平衡时间和空间的使用效率。尤其在内存资源有限的系统中,空间复杂度显得尤为重要。

这篇关于时间复杂度、空间复杂度,这里一次讲清楚的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

服务器集群同步时间手记

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,

【高等代数笔记】线性空间(一到四)

3. 线性空间 令 K n : = { ( a 1 , a 2 , . . . , a n ) ∣ a i ∈ K , i = 1 , 2 , . . . , n } \textbf{K}^{n}:=\{(a_{1},a_{2},...,a_{n})|a_{i}\in\textbf{K},i=1,2,...,n\} Kn:={(a1​,a2​,...,an​)∣ai​∈K,i=1,2,...,n

(function() {})();只执行一次

测试例子: var xx = (function() {     (function() { alert(9) })(); alert(10)     return "yyyy";  })(); 调用: alert(xx); 在调用的时候,你会发现只弹出"yyyy"信息,并不见弹出"10"的信息!这也就是说,这个匿名函数只在立即调用的时候执行一次,这时它已经赋予了给xx变量,也就是只是

算法复杂度的简单介绍

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

flume系列之:记录一次flume agent进程被异常oom kill -9的原因定位

flume系列之:记录一次flume agent进程被异常oom kill -9的原因定位 一、背景二、定位问题三、解决方法 一、背景 flume系列之:定位flume没有关闭某个时间点生成的tmp文件的原因,并制定解决方案在博主上面这篇文章的基础上,在机器内存、cpu资源、flume agent资源都足够的情况下,flume agent又出现了tmp文件无法关闭的情况 二、