首页 > 其他分享 >浅谈时间复杂度与空间复杂度

浅谈时间复杂度与空间复杂度

时间:2023-07-19 12:45:01浏览次数:28  
标签:浅谈 int 代码 算法 时间 空间 复杂度

算法的时间与空间复杂度(一看就懂)

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

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

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

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

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

一、时间复杂度

我们想要知道一个算法的「时间复杂度」,很多人首先想到的的方法就是把这个算法程序运行一遍,那么它所消耗的时间就自然而然知道了。

这种方式可以吗?当然可以,不过它也有很多弊端。
这种方式非常容易受运行环境的影响,在性能高的机器上跑出来的结果与在性能低的机器上跑的结果相差会很大。而且对测试时使用的数据规模也有很大关系。再者,并我们在写算法的时候,还没有办法完整的去运行呢。

因此,另一种更为通用的方法就出来了:「 大O符号表示法 」,即 T(n) = O(f(n))

我们先来看个例子:

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

通过「 大O符号表示法 」,这段代码的时间复杂度为:O(n) ,为什么呢?

在 大O符号表示法中,时间复杂度的公式是: T(n) = O( f(n) ),其中f(n) 表示每行代码执行次数之和,而 O 表示正比例关系,这个公式的全称是:算法的渐进时间复杂度

我们继续看上面的例子,假设每行代码的执行时间都是一样的,我们用 1颗粒时间 来表示,那么这个例子的第一行耗时是1个颗粒时间,第三行的执行时间是 n个颗粒时间,第四行的执行时间也是 n个颗粒时间(第二行和第五行是符号,暂时忽略),那么总时间就是 1颗粒时间 + n颗粒时间 + n颗粒时间 ,即 (1+2n)个颗粒时间,即: T(n) = (1+2n)*颗粒时间,从这个结果可以看出,这个算法的耗时是随着n的变化而变化,因此,我们可以简化的将这个算法的时间复杂度表示为:T(n) = O(n)

为什么可以这么去简化呢,因为大O符号表示法并不是用于来真实代表算法的执行时间的,它是用来表示代码执行时间的增长变化趋势的。

所以上面的例子中,如果n无限大的时候,T(n) = time(1+2n)中的常量1就没有意义了,倍数2也意义不大。因此直接简化为T(n) = O(n) 就可以了。

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

  • 常数阶O(1)
  • 对数阶O(logN)
  • 线性阶O(n)
  • 线性对数阶O(nlogN)
  • 平方阶O(n²)
  • 立方阶O(n³)
  • K次方阶O(n^k)
  • 指数阶(2^n)

上面从上至下依次的时间复杂度越来越大,执行的效率越来越低。

下面选取一些较为常用的来讲解一下(没有严格按照顺序):

  1. 常数阶O(1)

无论代码执行了多少行,只要是没有循环等复杂结构,那这个代码的时间复杂度就都是O(1),如:

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

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

  1. 线性阶O(n)

这个在最开始的代码示例中就讲解过了,如:

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

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

  1. 对数阶O(logN)

还是先来看代码:

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

从上面代码可以看到,在while循环里面,每次都将 i 乘以 2,乘完之后,i 距离 n 就越来越近了。我们试着求解一下,假设循环x次之后,i 就大于 2 了,此时这个循环就退出了,也就是说 2 的 x 次方等于 n,那么 x = log2^n
也就是说当循环 log2^n 次以后,这个代码就结束了。因此这个代码的时间复杂度为:O(logn)

  1. 线性对数阶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;
    }
}
  1. 平方阶O(n²)

平方阶O(n²) 就更容易理解了,如果把 O(n) 的代码再嵌套循环一遍,它的时间复杂度就是 O(n²) 了。
举例:

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

这段代码其实就是嵌套了2层n循环,它的时间复杂度就是 O(n*n),即 O(n²)
如果将其中一层循环的n改成m,即:

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

那它的时间复杂度就变成了 O(m*n)

  1. 立方阶O(n³)K次方阶O(n^k)

参考上面的O(n²) 去理解就好了,O(n³)相当于三层n循环,其它的类似。

除此之外,其实还有 平均时间复杂度、均摊时间复杂度、最坏时间复杂度、最好时间复杂度 的分析方法,有点复杂,这里就不展开了。

二、空间复杂度

既然时间复杂度不是用来计算程序具体耗时的,那么我也应该明白,空间复杂度也不是用来计算程序实际占用的空间的。

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一个量度,同样反映的是一个趋势,我们用 S(n) 来定义。

空间复杂度比较常用的有:O(1)、O(n)、O(n²),我们下面来看看:

  1. 空间复杂度 O(1)

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

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

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

  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)

以上,就是对算法的时间复杂度与空间复杂度基础的分析。

标签:浅谈,int,代码,算法,时间,空间,复杂度
From: https://www.cnblogs.com/yangyezhuang/p/17565265.html

相关文章

  • 浅谈Java容器
    Java容器容器类是Java以类库的形式供用户开发程序时可直接使用的各种数据结构。所谓数据结构就是以某种方式将数据组织在一起,并存储在计算机中。数据结构不仅可以存储数据,还支持访问和处理数据的操作。在面向对象思想里,一种数据结构被认为是一个容器。数组是一种简单的数据结构,......
  • pagefile.sys是Windows操作系统中的一个系统文件,它用于实现虚拟内存功能 。虚拟内存是
    pagefile.sys是Windows操作系统中的一个系统文件,它用于实现虚拟内存功能。虚拟内存是一种由硬盘上的空间模拟出来的内存,它允许操作系统将物理内存(RAM)之外的空间用作扩展内存。当物理内存不足时,操作系统会将一部分数据从物理内存转移到pagefile.sys文件中,以释放物理内存空间给其他......
  • Oracle11G扩展表空间
    转载自:https://www.qycn.com/xzx/article/13650.html这篇文章主要给大家介绍“Oracle增加表空间的方法及具体步骤是什么”的相关知识,下文通过实际案例向大家展示操作过程,内容简单清晰,易于学习,有这方面学习需要的朋友可以参考,希望这篇“Oracle增加表空间的方法及具体步骤是什么”......
  • 色彩解锁:探索革命性的CSS color()函数和新的色彩空间
    Google在6月份发布了一篇新博客,介绍了CSS中的新颜色空间和函数,支持所有主流引擎。下面是文章的链接:NewCSScolorspacesandfunctionsinallmajorengineshttps://web.dev/color-spaces-and-functions/?ref=sidebar该文章展示了一些支持的色彩空间的例子。color()函数介绍:color......
  • 浅谈 OI 中各种合并操作
    前言合并操作一直是OI中一大考点,今天请各位跟着笔者来梳理一下各种合并操作。启发式合并几乎可以说是最经典的合并了。假定我们可以在\(O(k)\)的时间内往某个集合中插入一个数,那么我们就可以在\(O(n\lognk)\)的时间内合并若干个元素总量为\(n\)的集合。集合启发式......
  • 浅谈虚树优化线段树
    前言我们都知道动态开点权值线段树的空间复杂度是\(O(n\logV)\)的,但是很多题目中这样的空间是会被卡的,那我们能不能优化呢?实现看看下面这一棵树:在上图中,红色节点使我们平常会开的点。但是我们发现,其实只要维护绿色的点和红色的叶子结点。其实,绿色节点就是所有叶子结点......
  • 在MacOS中使用free up Purgeable space释放磁盘空间,CleanMacX里面自带这个功能
    当你的Mac硬盘空间不足时,macOS会自动将一些文件标记为"可清除"(Purgeable),这些文件包括已下载但未安装的软件、iCloudDrive中的文件、以及其他一些可以重新下载或重新生成的文件。你可以通过释放这些"可清除"空间来腾出磁盘空间。要释放Purgeable空间,可以按照以下步骤操作:打......
  • 浅谈oracle,mysql数据备份
    oracle备份 方案1:Navicat工具迁移1.1开启Navicat,打开工具-数据同步   1.2选定原数据源与需要迁移到的数据源  1.3选择下一步,比对后开始进行数据同步   方案2:数据库服务器迁移2.1登录源数据库切换用户su-oracle切换到临时目录cd/u01/app/oracle......
  • Oracle Temp表空间切换
    1.查看临时表空间情况--查看数据库默认表空间SELECTPROPERTY_NAME,PROPERTY_VALUEFROMDATABASE_PROPERTIESWHEREPROPERTY_NAME='DEFAULT_TEMP_TABLESPACE';--查看现有数据库临时表空间SELECTTABLESPACE_NAMEFROMDBA_TABLESPACESWHERECONTENTS='TEMPORARY......
  • Oracle表空间和数据文件
    表空间:tablespace表空间就是:存放数据库表、索引、等等对象的逻辑空间。oracle数据在安装并创建实例后,默认会自动创建多个表空间。ORACL默认表空间SYSTEM表空间存放oracle内部表和数据字典(各种视图、表),如表名、列名、用户名等。不要将自己的数据放到该表空间内。该表空间......