面试必问的时间复杂度到底怎么算

简介:

高级工程师title的我,最近琢磨着好好刷刷算法题更高级一些,然鹅,当我准备回忆大学和面试时候学的数据结构之时,我发现自己对这个算法复杂度的记忆只有OOOOOooo

文章收录在 GitHub JavaKeeper ,N线互联网开发必备技能兵器谱

算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。

那么我们应该如何去衡量不同算法之间的优劣呢?

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

  • 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述。
  • 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述。

因此,评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而,有的时候时间和空间却又是「鱼和熊掌」,不可兼得的,那么我们就需要从中去取一个平衡点。

时间复杂度

一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或「时间频度」。记为T(n)。

时间频度T(n)中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律,为此我们引入时间复杂度的概念。算法的时间复杂度也就是算法的时间度量,记作:T(n) = O(f(n))。它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称「时间复杂度」。

这种表示方法我们称为「 大O符号表示法 」,又称为渐进符号,是用于描述函数渐进行为的数学符号

常见的时间复杂度量级有:

  • 常数阶$O(1)$
  • 线性阶$O(n)$
  • 平方阶$O(n^2)$
  • 立方阶$O(n^3)$
  • 对数阶$O(logn)$
  • 线性对数阶$O(nlogn)$
  • 指数阶$O(2^n)$

常数阶$O(1)$

$O(1)$,表示该算法的执行时间(或执行时占用空间)总是为一个常量,不论输入的数据集是大是小,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1),如:

int i = 1;
int j = 2;
int k = i + j;

上述代码在执行的时候,它消耗的时候并不随着某个变量的增长而增长,那么无论这类代码有多长,即使有几万几十万行,都可以用$O(1)$来表示它的时间复杂度。

线性阶$O(n)$

$O(n)$,表示一个算法的性能会随着输入数据的大小变化而线性变化,如

for (int i = 0; i < n; i++) {
     j = i;
   j++;
}

这段代码,for循环里面的代码会执行n遍,因此它消耗的时间是随着n的变化而变化的,因此这类代码都可以用$O(n)$来表示它的时间复杂度。

平方阶$O(n^2)$

$O(n²)$ 表示一个算法的性能将会随着输入数据的增长而呈现出二次增长。最常见的就是对输入数据进行嵌套循环。如果嵌套层级不断深入的话,算法的性能将会变为立方阶$O(n^3)$,$O(n^4)$,$O(n^k)$以此类推

for(x=1; i<=n; x++){
   for(i=1; i<=n; i++){
       j = i;
       j++;
    }
}

指数阶$O(2^n)$

$O(2^n)$,表示一个算法的性能会随着输入数据的每次增加而增大两倍,典型的方法就是裴波那契数列的递归计算实现

int Fibonacci(int number)
{
    if (number <= 1) return number;

    return Fibonacci(number - 2) + Fibonacci(number - 1);
}

对数阶$O(logn)$

int i = 1;
while(i<n)
{
    i = i * 2;
}

上面的代码,在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了,直到i不小于n退出。我们试着求解一下,假设循环次数为x,也就是说 2 的 x 次方等于 n,则由2^x=n得出x=log₂n。因此这个代码的时间复杂度为$O(logn)$

线性对数阶$O(nlogn)$

线性对数阶$O(nlogn) $,就是将时间复杂度为对数阶$O(logn)$的代码循环n遍的话,那么它的时间复杂度就是 n * O(logN),也就是了$O(nlogn)$,如下,

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

除此之外,其实还有平均情况复杂度、最好时间复杂度、最坏时间复杂度。。。一般没有特殊说明的情况下,都是值最坏时间复杂度。


空间复杂度

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,一个算法所需的存储空间用f(n)表示。S(n)=O(f(n)),其中n为问题的规模,S(n)表示空间复杂度。

一个算法在计算机存储器上所占用的存储空间,包括存储算法本身所占用的存储空间,算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

一般情况下,一个程序在机器上执行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元。若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为O(1)。当一个算法的空间复杂度与n成线性比例关系时,可表示为$0(n)$,类比时间复杂度。

空间复杂度比较常用的有:O(1)、O(n)、O(n²)

空间复杂度 $O(1)$

如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)
举例:

int i = 1;
int j = 2;
++i;
j++;
int m = i + j;

代码中的 i、j、m 所分配的空间都不随着处理数据量变化,因此它的空间复杂度 S(n) = O(1)

空间复杂度 $O(n)$

int[] m = new int[n]
for(i=1; i<=n; ++i)
{
   j = i;
   j++;
}

这段代码中,第一行new了一个数组出来,这个数据占用的大小为n,这段代码的2-6行,虽然有循环,但没有再分配新的空间,因此,这段代码的空间复杂度主要看第一行即可,即 S(n) = O(n)


复杂度速查表

来源:https://liam.page/2016/06/20/big-O-cheat-sheet/ 源地址:https://www.bigocheatsheet.com/

图例

大-O 复杂度曲线

抽象数据结构的操作复杂度

数组排序

图操作

堆操作

参考

《大话数据结构》
https://zhuanlan.zhihu.com/p/50479555

目录
相关文章
|
9月前
|
Java Maven
Maven编译报错:Failed to execute goal org.apache.maven.plugins:maven-compiler-plugin:3.13.0:compile 解决方案
在执行Maven项目中的`install`命令时,遇到编译插件版本不匹配的错误。具体报错为:`maven-compiler-plugin:3.13.0`要求Maven版本至少为3.6.3。解决方案是将Maven版本升级到3.6.3或降低插件版本。本文详细介绍了如何下载、解压并配置Maven 3.6.3,包括环境变量设置和IDEA中的Maven配置,确保项目顺利编译。
10115 4
Maven编译报错:Failed to execute goal org.apache.maven.plugins:maven-compiler-plugin:3.13.0:compile 解决方案
计算机组成原理(9)----硬布线控制器
计算机组成原理(9)----硬布线控制器
405 1
|
9月前
|
机器学习/深度学习 人工智能 编解码
阿里云GPU云服务器优惠收费标准,GPU服务器优缺点与适用场景详解
随着人工智能、大数据分析和高性能计算的发展,对计算资源的需求不断增加。GPU凭借强大的并行计算能力和高效的浮点运算性能,逐渐成为处理复杂计算任务的首选工具。阿里云提供了从入门级到旗舰级的多种GPU服务器,涵盖GN5、GN6、GN7、GN8和GN9系列,分别适用于图形渲染、视频编码、深度学习推理、训练和高性能计算等场景。本文详细介绍各系列的规格、价格和适用场景,帮助用户根据实际需求选择最合适的GPU实例。
|
11月前
|
人工智能 JSON 自然语言处理
开源模型+Orchestrating Agents多智能体框架,易用、强大且可控
本文采用开源Qwen2.5-14B-instruct-GGUF来体验多智能体编排和交接,希望在体验多智能体编排和交接框架的同时,一起评估中小参数规模的模型(14B)能否较好的完成多智能体任务。
|
NoSQL 安全 关系型数据库
如何在短时间内完成MongoDB差异数据对比
NineData提供高效、安全、准确的MongoDB数据对比解决方案。它支持多种使用场景下的对比功能,包括一次性对比、周期性对比、全量数据对比和快速对比。NineData还提供简单易用的SaaS平台和可视化界面,以直观的图表和报告呈现对比结果。此外,NineData具备强劲的性能和稳定性,通过智能数据分片、批量混检和抽样检查等核心技术实现对比任务的高效运行。用户可以免费使用NineData的数据对比功能,并且平台通过高等级的安全认证保护企业的信息安全。
503 1
|
数据采集 XML 运维
什么是主数据管理?企业主数据管理方法论
主数据又被称为黄金数据,其价值高也非常重要。对企业来说,主数据的重要性如何强调都不为过,主数据治理是企业数据治理中最为重要的一环。主数据管理的内容包括 主数据管理标准、主数据应用标准 和 主数据集成服务标准 三大类。
|
运维 搜索推荐 Shell
Ansible自动化运维工具之个性化定制SSH连接登录端口(3)
Ansible自动化运维工具之个性化定制SSH连接登录端口(3)
396 0
|
SQL 分布式计算 Java
Spark 为什么比 Hive 快
Spark与Hive在数据处理上有显著区别。Spark以其内存计算和线程级并行提供更快的速度,但稳定性受内存限制。相比之下,Hive虽较慢,因使用MapReduce,其稳定性更高,对内存需求较小。在Shuffle方式上,Spark的内存 Shuffle 比Hive的磁盘 Shuffle 更高效。综上,Spark在处理速度和Shuffle上占优,Hive则在稳定性和资源管理上更胜一筹。
583 0
|
存储 算法
【数据结构】—时间复杂度or空间复杂度以及基础题目练习
【数据结构】—时间复杂度or空间复杂度以及基础题目练习
279 0
|
JavaScript 前端开发 Java
CocosCreator 面试题(十)Cocos Creator 内存管理
CocosCreator 面试题(十)Cocos Creator 内存管理
732 0