时间复杂度+常见复杂度解释

2023-11-20

前言

算法的效率

虽然计算机能快速的完成运算处理,但实际上,它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源。要想编写出能高效运行的程序,我们就需要考虑到算法的效率。
算法的效率主要由以下两个复杂度来评估:
时间复杂度:评估执行程序所需的时间。可以估算出程序对处理器的使用程度。
空间复杂度:评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。

设计算法时,一般是要先考虑系统环境,然后权衡时间复杂度和空间复杂度,选取一个平衡点。不过,时间复杂度要比空间复杂度更容易产生问题,因此算法研究的主要也是时间复杂度,不特别说明的情况下,复杂度就是指时间复杂度。

本文只分析时间复杂度

什么是时间复杂度

了解时间复杂度之前,先了解时间频度

时间频度

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

在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2)。

一句话:T(n)就是时间频度,表示算法执行的次数

问题:T(n)随着n的改变而改变

时间复杂度

时间复杂度 在刚才提到的时间频度中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此,我们引入时间复杂度概念。 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。

时间复杂度怎么算

  基本操作即算法中的每条语句(以;号作为分割),语句的执行次数也叫做语句的频度。在做算法分析时,一般默认为考虑最坏的情况。

1、计算出每条语句执行次数T(n)

求出代码中每条语句执行的次数

在做算法分析时,一般默认为考虑最坏的情况。

2、计算出T(n)的数量级

求T(n)的数量级,只要将T(n)进行如下一些操作:

忽略常量

低次幂和最高次幂的系数

令f(n)=T(n)的数量级。

3、用大O来表示时间复杂度

  当n趋近于无穷大时,如果lim(T(n)/f(n))的值为不等于0的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))。

只保留最高阶项,最高阶项存在且不是1,则去除与这个项相乘的常数。

前面提到的时间频度T(n)中,n称为问题的规模,当n不断变化时,时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律,为此我们引入时间复杂度的概念。一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数,记作T(n)=O(f(n)),它称为算法的渐进时间复杂度,简称时间复杂度

T(n)/f(n)的极限值为不等于零的常数什么意思?

首先你要知道T(n)是f(n)忽略常量、低次幂和最高次幂的系数。只保留能代表数量级的项。

所以T(n)肯定是小于等于f(n)的

那么,如果T(n)/f(n)的极限值等于0,那么就是说f(n)的增长趋势比T(n)大太多,那么就说明他们俩不是一个数量级的。

不是一个数量级什么意思呢?

就好比你玩LOL,你是黄铜1,他是黄铜3,虽然你比他高一点,但你们俩还是黄铜,是一个数量级的。。。大多数时候,通过段位就能判断你的水平,不会在意是你在你段位是1还是5。这里算法的时间复杂度也是一样,只保留核心项,其他的都去掉。

什么时候不是一个数量级呢?等你上白银或者黄金的时候,那就不是一个数量级的。。。

一个算法的执行时间与哪些因素有关

衡量一个算法的好坏不能简单的从这个算法所花费的时间来衡量。因为这个时间受多种因素影响。一般来说一个算法花费的时间有以下4点

  • 计算机执行的速度->硬件层面
  • 编译产生的代码质量->软件层面
  • 算法的好坏(算法使用的策略)
  • 问题规模

在给定软硬件环境下,其实就是你在自己电脑上写算法的时候,算法执行时间只受算法本身的好坏和要处理的问题的规模影响。这样就将4个影响因素减少为2个,简化了问题

我们继续分析,

给定问题规模n之后,优秀的算法可能执行几次就搞定了,一般的算法可能执行很多很多次才搞定;

当给定算法时,问题规模n很小时,可能执行几次就搞定,而n很大时,就得执行很多次了。

所以算法优劣和问题规模n改变时,执行次数(基本操作数)将改变,所以执行次数就是算法优劣和问题规模n的函数。

既然执行时间受算法好坏和问题规模n的影响,那么执行时间就是它俩的函数。

要比较两个函数的增长情况,最好的办法是比较函数的一阶导,这样最精确,但是考虑到很多时候只需要大体了解算法的优劣就可以了,所以我们就直接考察对增长速度影响最大的一项,这一项就是函数的最高阶数。为了说明最高阶数对函数增长影响最明显,我们看两幅图。

图中4条曲线分别表示4种不同的执行次数表达式,从图中可以看出,只要最高项的阶数相同,4种表达式值受其他项的影响很小,随着n增大,几乎可以忽略不计,甚至可以忽略与最高项相乘的常数。

既然可以只考虑最高项的阶数,以简化问题,达到估算的目的,为何不这样做呢?

那总得给这种情况一个恰当的表示方式吧?和其他领域一样,还得用符号来表示,这个符号就是大名鼎鼎的O符号

推导大O阶有一下三种规则:

  1. 用常数1取代运行时间中的所有加法常数
  2. 只保留最高阶项
  3. 去除最高阶的常数

一般我们我们评估一个算法都是直接评估它的最坏的复杂度。

时间复杂度是一个量级的概念,而不是具体的值,比如O(5n)的量级是n,因为这个时间复杂度函数内最高量级是变量n的一次方

常见时间复杂度

下图来自维基百科

常数级别O(1)

O(1):算法复杂度和问题规模无关。换句话说,哪怕你拿出几个PB的数据,我也能一步到位找到答案。

理论上哈希表就是O(1)。因为哈希表是通过哈希函数来映射的,所以拿到一个关键字,用哈希函数转换一下,就可以直接从表中取出对应的值。和现存数据有多少毫无关系,故而每次执行该操作只需要恒定的时间(当然,实际操作中存在冲突和冲突解决的机制,不能保证每次取值的时间是完全一样的)。

执行次数

N=10,大约执行1次

N=100,大约执行1次

N=1000,大约执行1次

N=10000,大约执行1次

对数级别O(logN)

Tips:log的底数在大O符号的中是省去的。常见的底数为2

O(logN):算法复杂度和问题规模是对数关系。换句话说,数据量大幅增加时,消耗时间/空间只有少量增加(比如,当数据量从2增加到2^64时,消耗时间/空间只增加64倍)

执行次数

底数为2的情况

N=10,大约执行3次

N=100,大约执行7次

N=1000,大约执行10次

N=10000,大约执行13次

代码

int number = 1; // 语句执行一次
while (number < n) { // 语句执行logn次
  // 这里的2是log的底数
  // 底数在大O符号中是省去的
  number *= 2; // 语句执行logn次
}

线性级别O(N)

O(n):算法复杂度和问题规模是线性关系。换句话说,随着样本数量的增加,复杂度也随之线性增加

执行次数

N=10,大约执行10次

N=100,大约执行100次

N=1000,大约执行1000次

N=10000,大约执行10000次

代码

int i =0; // 语句执行一次
while (i < n) { // 语句执行n次
  print(i); //语句执行n次
  i++; // 语句执行n次
}

这个算法中代码总共执行了 3n + 1次,根据规则 2->3,因此该算法的时间复杂度是O(n)。

线性对数级别O(NlogN)

O(logn)的算法复杂度,典型的比如二分查找。设想一堆试卷,已经从高到底按照分数排列了,我们现在想找到有没有59分的试卷。怎么办呢?先翻到中间,把试卷堆由中间分成上下两堆,看中间这份是大于还是小于59,如果大于,就留下上面那堆,别的丢掉,如果小于,就留下下面那堆,丢掉上面。然后按照同样的方法,每次丢一半的试卷,直到丢无可丢为止。

假如有32份试卷,你丢一次,还剩16份 ,丢两次,还剩下8 份,丢三次,就只剩下4份了,可以这么一直丢下去,丢到第五次,就只剩下一份了。而 log_2(32) = 5 。也就是我们一次丢一半,总要丢到只有一份的时候才能出结果,如果有n份,那么显然我们就有:

\frac{n}{2^k} = 1\Rightarrow k = log_2 n

也就是大约需要 log_2 n 次,才能得出“找到”或者“没找到”的结果。当然你说你三分查找,每次丢三分之二可不可以?当然也可以,但是算法复杂度在这里是忽略常数的,所以不管以2为底,还是以什么数为底,都统一的写成 log(n)的形式。

理解了这一点,就可以理解快速排序为什么是 O(nlogn)了。比如对一堆带有序号的书进行排序,怎么快呢?就是随便先选一本,然后把号码大于这本书的扔右边,小于这本书的扔左边。因为每本书都要比较一次,所以这么搞一次的复杂度是 O(n),那么快排需要我们搞多少次呢?这个又回到了二分查找的逻辑了,每次都把书堆一分为二,请问分多少次手里才能只剩下一本书呢?答案还是 logn。而从代码的角度来说,在到达大小为一的数列之前,我们也是需要作 logn次嵌套的调用。

执行次数

底数为2的情况

N=10,大约执行33次

N=100,大约执行664次

N=1000,大约执行9966次

N=10000,大约执行132877次

平方级别O(N^2)

O(n^2)计算的复杂度随着样本个数的平方数增长。这个例子在算法里面,就是那一群比较挫的排序,比如冒泡等等。 

执行次数

N=10,大约执行100次

N=100,大约执行10000次

N=1000,大约执行1000000次

N=10000,大约执行100000000次

代码

for (int i = 0; i < n; i++) { // 语句执行n次
  for (int j = 0; j < n; j++) { // 语句执行n^2次
     print('I am here!'); // 语句执行n^2
  }
}

上面的嵌套循环中,代码共执行 2*n^2 + n,则f(n) = n^2。所以该算法的时间复杂度为O(n^2 )

指数级别O(2^N)

如果一个算法的运行时间是指数级的(exponential),一般它很难在实践中使用

执行次数

N=10,大约执行1024次

N=100,大约执行2^100次

N=1000,大约执行2^1000次

N=10000,大约执行2^10000次

排序算法计算

这里并不是详细讲排序算法,只讲他们的复杂度是什么算出来的。

来自:https://www.zhihu.com/question/21387264/answer/422740592

冒泡排序

对于数组中的每一个数,我们比较它和右边的邻居的大小关系,邻居小则交换。从数组的最右端开始,最后一个数(array[n - 1])没有右邻居,所以我们从倒数第二右(array[n - 2])开始,它最多跟最后一个数比较并交换 1 次;接下来是 array[n - 3],它右边有 2 个邻居,所以它最多比较并交换 2 次……以此类推,直到最左边的数 array[0],它右边有 n - 1 个邻居,所以它最多比较并交换 n - 1 次。综上所述,算法的总比较次数就是 1+2+3+...+(n-1)=\frac{n^2}{2} 。忽略系数,所以它具有 O(n^2) 的时间复杂度。

选择排序。我们每次从数组中选出一个最小值并放在最左边。第一轮从 n 个数里选出一个最小值,所以我们需要挨个比较 n 个数;第二轮从 n - 1 个数里选出一个最小值,我们需要挨个比较 n - 1 个数……以此类推,算法的总比较次数就是 n+(n-1)+(n-2)+...+2+1 =\frac{n(n+1)}{2} =\frac{n^2}{2}+\frac{n}{2} 。忽略系数和低阶项,我们说它的时间复杂度是 O(n^2)

归并排序

这是一个分治的过程,并且我们通常使用递归来实现。为了分析递归,我们应该画出递归树,举例如下:

Split 0         8 7 6 5 4 3 2 1
Split 1        8 7 6 5 | 4 3 2 1
Split 2      8 7 | 6 5 | 4 3 | 2 1
Split 3  8 | 7 | 6 | 5 | 4 | 3 | 2 | 1
------------------------------------------
Merge 0  8 | 7 | 6 | 5 | 4 | 3 | 2 | 1
Merge 1      7 8 | 5 6 | 3 4 | 1 2
Merge 2        5 6 7 8 | 1 2 3 4
Merge 3         1 2 3 4 5 6 7 8

将整个归并排序分为分割合并两个过程来看。

分割过程

对于分割过程(分割线以上),每分割一次,我们就会分别对左右两部分执行相同的逻辑,即递归调用这两部分。所以我们来看分割部分一共有多少次函数调用:split 0 层有 1 次函数调用;split 1 层是第 1 次分割,对左右两半分别调用 1 次函数,因此该层一共有 2 次函数调用;以此类推,split 2 层有 4 次调用、split 3 层有 8 次调用……所以整个分割过程一共调用了 1+2+4+...+n=2n-1 次函数(首项为 1、公比为 2、末项为 n 的等比数列求和)。忽略系数和常数项,分割过程具有 O(n) 的时间复杂度。

合并过程

再来看合并过程(分割线以下)。对于两个排好序的子部分,将其合并需要对两个子部分中的每一个数逐一比较。因此,merge 0 层我们需要合并 8 组,每组只有一个数,不妨算作“逐一比较”1 次,所以该层的总比较次数为 8 次;类似地,merge 1 层有 4 组,组与组之间两两比较,该层的总比较次数为 4 x 2 = 8 次……以此类推,合并过程中每层都需要比较 n 次,总层数为 \log_2n+1 ,所以总比较次数就是 n(\log_2n+1) 。忽略底数和低阶项,我们就得到了合并过程的时间复杂度 O(n\log n) 。

所以对于整个归并排序,总时间复杂度为分割+合并,即 O(n+n\log n),忽略低阶项,就是 O(n\log n) 。

快速排序

也是一个分治的过程。这里重点强调最坏复杂度 O(n^2) 和平均复杂度 O(n\log n)是怎么算出来的。快排的过程可以概括为,先从数组里随机选出一颗“钉子”(pivot),遍历整个数组,将这颗钉子放到自己应有的位置上,而且此时此刻,钉子左边那一半虽然还没排好序,但它们全部都比钉子小,同理钉子右边那一半全部都比钉子大但也还没排好序。接下来,我们分别对钉子的左右两部分执行刚才的逻辑,即递归调用快排过程,直到不能再分割为止。所以我们不难发现,随机选择的钉子就是整个快排最大的变数。

最差情况

Quick sort: worst case scenario

Layer 0  [8 7 6 5 4 3 2 1]
                        p
Layer 1  1 [8 7 6 5 4 3 2]
                        p
Layer 2  1 2 [8 7 6 5 4 3]
                        p
......
*p: the pivot

快排的最坏情况就是,假设我们每一次挑出来的钉子都非常不走运,该轮遍历完后这颗钉子恰好位于数组的一端,此时分别递归钉子的左右两边就会变成只能递归一边,因为另一边是空的。换言之,在这种次次不走运的极端情况下,每轮挪钉子的过程就退化成了一个选择排序。前面我们已经分析过选择排序的时间复杂度是 O(n^2),因此快排的最坏时间复杂度是 O(n^2) 。

平均情况

Quick sort: average scenario

Layer 0  [11 10 9 8 7 6 5 4 3 2 1]
                      p
Layer 1  [5 4 3 2 1] 6 [11 10 9 8 7]
              p               p
Layer 2  [2 1] 3 [5 4] 6 [8 7] 9 [11 10]
          p       p       p       p
......
*p: the pivot

快排的平均情况就是,假设我们每一次挑出来的钉子不偏不倚,遍历完后正好位于数组的正中央,显然这一轮遍历了 n 个元素。接下来,分别递归钉子的左右两边,即分别遍历两组 n/2 个元素,该轮总计遍历了 2 x n/2 = n 个元素……以此类推,每次递归钉子都在正中间,每层我们都要遍历 n 个元素,每次递归都是均匀二分,那么就像上面的归并排序一样,一共会有 \log_2n+1 层,所以在这种情况下整个算法一共遍历 n(\log_2n+1) 次,也就是 O(n\log n) 的时间复杂度。

堆排序

虽然总体复杂度也是 O(n\log n) ,但它的建堆过程是 O(n) ,很多人在这里犯错。接下来我们用高一数学推导建堆过程的时间复杂度。

首先将原数组用堆结构表示出来,例如下图的二叉堆:

Layer 0         15
Layer 1       14  13
Layer 2    12 11  10 9
Layer 3  8 7 6 5 4 3 2 1

建堆(heapification)过程概括来讲,就是从当前堆的最后一个父节点开始,检查该父节点是否与其左右子节点满足堆序性(heap property),不满足则一路向下交换,并挨个对每一个父节点重复这个过程。从图中我们很容易看出 n 个元素组成的堆一共有 \log_2n 层。仔细观察不难发现,排位靠下的父节点,只需要较少的次数就能换到最下面;而靠上的父节点,则要交换更多次才能换到最下面。在最坏情况下,假设所有父节点都需要换到最下面,为方便起见我们令堆的总层数 \log_2n=t ,可得

Layer 0 有 2^0=1 个父节点,换到最底(最坏情况)需要交换 t-1 次;

Layer 1 有 2^1=2 个父节点,换到最底需要交换 t-2 次;

……

倒数第二层有 2^{t-2} 个父节点,换到最底需要交换 1 次;

最后一层全是叶子节点,不交换。

综上可得建堆过程的总交换次数

S_n=2^0(t-1)+2^1(t-2)+2^2(t-3)+...+2^{t-3}\cdot2+2^{t-2}\cdot1

不难看出,这是一个我们在高中已经玩烂了的差比数列(等比x等差的数列),错位相减即可求得该数列的和:

2S_n=2^1(t-1)+2^2(t-2)+...+2^{t-3}\cdot3+2^{t-2}\cdot2+2^{t-1}\cdot1

以上两式相减得

2S_n-S_n=S_n

=-(t-1)+[2^1+2^2+...+2^{t-2}+2^{t-1}]

=2^t-t-1

代入 t=\log_2n可得建堆过程的总交换次数

S_n=n-\log_2n-1

忽略低阶项和常数项,建堆的时间复杂度为 O(n)

nlogn,难道这是排序算法的极限了吗?

很遗憾,nlogn已经是比较排序算法的极限了。

具体可以看知乎的讨论https://www.zhihu.com/question/24516934

参考

https://blog.csdn.net/u010402786/article/details/51435735

https://juejin.im/post/58d15f1044d90400691834d4

https://www.zhihu.com/question/21387264

https://www.zhihu.com/question/20196775

https://blog.csdn.net/zolalad/article/details/11848739

https://www.cnblogs.com/gaochundong/p/complexity_of_algorithms.html

https://blog.csdn.net/u010402786/article/details/51435735

本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

时间复杂度+常见复杂度解释 的相关文章

  • 算法:双指针

    双指针 双指针是一种思想或一种技巧并不是特别具体的算法 具体就是用两个变量动态存储两个结点 来方便我们进行一些操作 通常用在线性的数据结构中 特别是链表类的题目 经常需要用到两个或多个指针配合来记忆链表上的节点 完成某些操作 常见的双指针方
  • 以OpenGL/ES视角介绍gfx-hal(Vulkan) Shader/Program接口使用

    文档列表见 Rust 移动端跨平台复杂图形渲染项目开发系列总结 目录 背景 The right way to tackle this in Vulkan is to use resource descriptors A descriptor
  • 数据结构中常见的树(BST二叉搜索树、AVL平衡二叉树、RBT红黑树、B-树、B+树、B*树)

    原文 http blog csdn net sup heaven article details 39313731 数据结构中常见的树 BST二叉搜索树 AVL平衡二叉树 RBT红黑树 B 树 B 树 B 树 转载 2014年09月16日
  • 数据结构之链表与线性表

    数据结构之链表与线性表 线性表 顺序线性表 顺序表 顺序线性表 使用数组实现 一组地址连续的存储单元 数组大小有两种方式指定 一是静态分配 二是动态扩展 优点 随机访问特性 查找O 1 时间 存储密度高 逻辑上相邻的元素 物理上也相邻 缺点
  • 第二十八节、基于深度学习的目标检测算法的综述(附代码,并附有一些算法英文翻译文章链接))...

    在前面几节中 我们已经介绍了什么是目标检测 以及如何进行目标检测 还提及了滑动窗口 bounding box 以及IOU 非极大值抑制等概念 这里将会综述一下当前目标检测的研究成果 并对几个经典的目标检测算法进行概述 本文内容来自基于深度学
  • PCL—低层次视觉—点云分割(RanSaC)

    点云分割 点云分割可谓点云处理的精髓 也是三维图像相对二维图像最大优势的体现 不过多插一句 自Niloy J Mitra教授的Global contrast based salient region detection出现 最优分割到底鹿死
  • 微软2013暑假实习生笔试题

    自己mark一下 以作后备 下面提交原文链接 原文博客 部分题目答案不确定 会持续更新 1 Which of the following calling convention s support s supportvariable leng
  • 逆波兰表达式求值(C语言实现)

    实验项目 从文本文件输入任意一个语法正确的 中缀 表达式 显示并保存该表达式 利用栈结构 把上述 中缀 表达式转换成后缀表达式 并显示栈的状态变化过程和所得到的后缀表达式 利用栈结构 对上述后缀表达式进行求值 并显示栈的状态变化过程和最终结
  • DNG格式解析

    Author Maddock Date 2015 04 22 转载请注明出处 http www cnblogs com adong7639 p 4446828 html DNG格式基本概念 DNG格式是在TIFF的基础上扩展出来的 要了解D
  • 递归算法中的时间复杂度分析

    对于一种算法的时间复杂度分析还是特别重要的 在一些非递归算法中 我们仅仅看运算次数最多的那一行代码可能执行多少次就可以 实际就是看在循环中变量的变化 但是对于递归算法中该怎么分析呢 下面介绍几种递归函数中的算法时间复杂度分析的方法 0 递推
  • 手把手教你实现一个向量

    文章目录 什么是向量 向量提供哪些接口 实现 宏定义 定义类 成员变量 构造函数与析构函数 构造函数 析构函数 成员函数 size get r put r e expand insert r e remove lo hi remove r
  • Python 实现列队

    1 列队定义 队列是项的有序结合 其中添加新项的一端称为队尾 移除项的一端称为队首 当一个元素从队尾进入队列时 一直向队首移动 直到它成为下一个需要移除的元素为止 最近添加的元素必须在队尾等待 集合中存活时间最长的元素在队首 这种排序成为
  • 算法系列15天速成——第八天 线性表【下】

    一 线性表的简单回顾 上一篇跟大家聊过 线性表 顺序存储 通过实验 大家也知道 如果我每次向 顺序表的头部插入元素 都会引起痉挛 效率比较低下 第二点我们用顺序存储时 容 易受到长度的限制 反之就会造成空间资源的浪费 二 链表 对于顺序表存
  • 算法学习——贪心算法之币种统计

    算法描述 币种统计 单位给每一位员工发工资 精确到元 为了保证不临时换零钱 使得每个员工取款的张数最少 在取工资前统计所有员工所需要的各种票面的张数 约定票种为100 50 20 10 5 2 1元 并验证币种统计是否正确 算法思路 算法描
  • 二叉树结构的建立与遍历

    实验项目 1 编写建立二叉树的二叉链表存储结构 左右链表示 的程序 并以适当的形式显示和保存二叉树 2 完成二叉树的7种遍历操作 3 给定一个二叉树 编写算法完成下列应用 1 判断其是否为完全二叉树 2 求二叉树中任意两个结点的公共祖先 输
  • 索引优化之Explain 及慢查询日志

    索引 本质是数据结构 简单理解为 排好序的快速查找数据结构 以索引文件的形式存储在磁盘中 目的 提高数据查询的效率 优化查询性能 就像书的目录一样 优势 提高检索效率 降低IO成本 排好序的表 降低CPU的消耗劣势 索引实际也是一张表 该表
  • 雪糕的最大数量 排序+贪心

    雪糕的最大数量 雪糕的最大数量 题目描述 样例 数据范围 思路 代码 题目描述 夏日炎炎 小男孩 Tony 想买一些雪糕消消暑 商店中新到 n 支雪糕 用长度为 n 的数组 costs 表示雪糕的定价 其中 costs i 表示第 i 支雪
  • C++ AVL树(四种旋转,插入)

    C AVL树 四种旋转 插入 一 AVL树的概念及性质 二 我们要实现的大致框架 1 AVL树的节点定义 2 AVL树的大致框架 三 插入 1 插入逻辑跟BST相同的那一部分 2 修改平衡因子
  • 排序:计数排序

    一 概念 计数排序是非比较排序 是对哈希直接定址法的变形应用 二 思想 利用数组统计相同数据出现的次数 例如整型数据m出现n次 就在数组m位置记录数据为n 最后从头遍历数组打印数据即可 通俗来讲就是 数组下标即为数据 下标所指位置的值即为数
  • 高精度运算合集,加减乘除,快速幂,详细代码,OJ链接

    文章目录 零 前言 一 加法 高精度加法步骤 P1601 A B 二 减法 高精度减法步骤

随机推荐

  • Flink_05_状态(个人总结)

    声明 1 本文为我的个人复习总结 并非那种从零基础开始普及知识 内容详细全面 言辞官方的文章 2 由于是个人总结 所以用最精简的话语来写文章 3 若有错误不当之处 请指出 状态 状态就是一块内存 一个变量 如果要访问历史窗口 或批次 的数据
  • 运动规划入门

    原创文章 作者 tloinny 如若转载 请注明出处 古月居 https www guyuehome com 5652 感谢古月老师 古 月给的机会 让笔者有幸成为古月居签约作者 此后笔者将在古月居发布更多Robotic相关的博文 当然我也
  • gcc搜索动态链接库的路径优先级排序

    GCC运行时 Linux动态链接库的搜索路径按优先级排序为 1 编译目标代码时 Wl rpath 指定的动态库搜索路径 当指定多个动态库搜索路径时 路径之间用冒号 分隔 2 环境变量 LD LIBRARY PATH 指定的动态库搜索路径 3
  • 泊松重建算法原理介绍

    目录 1 泊松重建算法 2 泊松重建核心思想及原理 3 泊松算法流程 本文出自CSDN点云侠 原文链接 爬虫自重 把自己当个人 1 泊松重建算法 泊松重建是Kazhdan M在2006年提出的基于八叉树和泊松方程的一种网格三维重建算法 其本
  • python 爬取google总结

    1 问题 目前主流的搜索引擎 非google莫属 但其对于非法 流量异常 爬虫 请求的封锁也是异常严厉 本人前段时间有个脚本用到了谷歌搜索 具体见python之由公司名推算出公司官网 余弦相似度 当时直接使用的是一个python开源项目 但
  • Python3:官方文档的链接

    1 numpy https www numpy org cn article https numpy org 2 pandas https pandas pydata org 3 matplotlib https matplotlib or
  • 字符串最后一个单词的长度

    描述 计算字符串最后一个单词的长度 单词以空格隔开 字符串长度小于5000 输入描述 输入一行 代表要计算的字符串 非空 长度小于5000 输出描述 输出一个整数 表示输入字符串最后一个单词的长度 示例1 输入 hello nowcoder
  • 手把手教你开发第一个HarmonyOS (鸿蒙)移动应用

    移动应 开发的介绍 移动应 开发 Android IOS HarmonyOS 鸿蒙 HarmonyOS介绍 文档概览 HarmonyOS应用开发官网 2 1 系统的定义 2 1 1 系统的定位 HarmonyOS有三 特征 搭载该操作系统的
  • 快手APP内测「AI对话」

    快手 APP 现在有了 AI 对话能力 8 月 18 日晚 快手公布基于自研大语言模型应用的最新进展 快手 AI 对话 功能已经在快手 APP 安卓版本开放内测 参与测试的用户只需要在最新正式版本的 APP 上点击快手搜索首页右上角 AI
  • 常用Shell命令汇总-用户和用户组管理

    不知道大家平时有没有跟我一样的感受 就是很多shell命令自己其实用过 但时间一久又忘记了 导致又要到处百度 开始写这个系列的目的第一是为了总结 第二是为了以后忘记时可以直接到这找哈哈哈哈哈 平时在百度时还发现一个问题 就是其实我只想要最常
  • 2023华为OD机试真题【机房布局/模拟】

    题目描述 小明正在规划一个大型数据中心机房 为了使得机柜上的机器都能正常满负荷工作 需要确保在每个机柜边上至少要有一个电箱 为了简化题目 假设这个机房是一整排 M表示机柜 I表示间隔 请你返回这整排机房 至少需要多少个电箱 如果无解请返回
  • 安装 Android Studio

    安装 Android Studio 只需轻松点击几下 您需要已下载 Android Studio Windows 如需在 Windows 系统中安装 Android Studio 请执行以下操作 启动您下载的 exe 文件 根据安装向导的指
  • npz,npy的输入和读取np.load和np.save

    np load和np save 是读写磁盘数组数据的两个主要函数 默认情况下 数组是以未压缩的原始二进制格式保存在扩展名为 npy的文件中 np savez 如果你想将多个数组保存到一个文件中的话 可以使用numpy savez函数 sav
  • 数学建模中的经典问题-旅行商(TSP)问题

    1 相关理论 2 算法流程 3 代码实现 4 结果显示 1 相关理论 旅行商 TSP 问题是数学建模中的经典问题 它是一个典型的NP完全问题 TSP问题可描述为 已知n个城区相互之间的距离 某一旅行商从城市出发访问每个城市一次且仅一次 最后
  • ios -Unity3D的EasyAR集成到已经有项目中。

    近期 在做AR这一块 用EasyAR集成到iOS端 由于现在到项目已经上线 下一版本要做一个AR功能 于是迫于需求需要 自己研究和翻阅读好多集成到资料 通过整理分出几个重要到模块 其中在这里指出Xcode9版本确实好坑 建议弃坑 该用稍微好
  • android studio agpbi error,Android Studio 3.1.1 打Jar包出现AGPBI异常解决

    今天 写好Demo兴致勃勃准备打个Jar包在Unity中测试下 不料 突然出现AGPBI这个异常 日志如下 AGPBI kind error text Program type already present android support
  • Android Recyclerview焦点变化问题导致下拉刷新视觉卡顿

    如题 最近做项目时偶然发现了一个Recyclerview嵌套Recycleview的问题 业务模块是订单列表 涉及到一个订单包含多个子订单的情况 所以考虑使用嵌套来展示页面 这一切都是正常的 没有任何问题 然而 随着业务的展开需要查看详情单
  • 自己写的PLC编程软件,和FANUC PMC功能基本保持一致

    自己写的PLC编程软件 和FANUC PMC功能基本保持一致 下载地址 免积分 链接 pan baidu com s 162 GcF7wh SNT3McATPPmg 提取码 1234 https download csdn net down
  • 基于ShuffleNetv2-YOLOv4模型的目标检测

    目录 1 引言 摘要 1 1 说明 1 2替换完成的工程请参考gitee 2 网络结构基础 2 1YOLOv3 2 1 YOLOv4算法 2 3 ShuffleNetv2 2 4 替换后的网络结构 3 实验结果 3 1实验环境配置及数据集介
  • 时间复杂度+常见复杂度解释

    前言 算法的效率 虽然计算机能快速的完成运算处理 但实际上 它也需要根据输入数据的大小和算法效率来消耗一定的处理器资源 要想编写出能高效运行的程序 我们就需要考虑到算法的效率 算法的效率主要由以下两个复杂度来评估 时间复杂度 评估执行程序所