2025年gjk算法复杂度（算法复杂度logn）

大家好，我是讯享网，很高兴认识大家。

算法在编写成可执⾏程序后，运⾏时需要耗费时间资源和空间(内存)资源。因此衡量⼀个算法的好坏，⼀般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量⼀个算法的运⾏快慢，⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外间。在计算机发展的早期，计算机的存储容量很⼩。所以对空间复杂度很是在乎。但是经过计算机⾏业的迅速发展，计算机的存储容量已经达到了很⾼的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。

定义：在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？

1. 因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。

2. 同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。

3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

这个T(N)函数式计算了程序的执⾏次数。

讯享网

Func1 执⾏的基本操作次数： T (N) = N2 + 2 ∗ N + 10

实际中我们计算时间复杂度时，计算的也不是程序的精确的执⾏次数，精确执⾏次数计算起来还是很⿇烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执⾏次数意义也不⼤，因为我们计算时间复杂度只是想⽐较算法程序的增⻓量级，也就是当N不断变⼤时T(N)的差别，上⾯我们已经看到了当N不断变⼤时常数和低阶项对结果的影响很⼩，所以我们只需要计算程序能代表增⻓量级的⼤概执⾏次数，复杂度的表⽰通常使⽤⼤O的渐进表⽰法。

大O：⽤于描述函数渐进⾏为的数学符号

讯享网
通过以上⽅法，可以得到 Func1 的时间复杂度为： O(N2)

讯享网

Func2执⾏的基本操作次数： T (N) = 2N + 10

根据推导规则第3条得出 Func2的时间复杂度为： O(N)

Func3执⾏的基本操作次数：T (N) = M + N

因此：Func2的时间复杂度为： O(M+N)

若M>>N O(M)

若M<<N O(N)

若M约等于N O(M+N)

讯享网

Func4执⾏的基本操作次数：T (N) = 100

根据推导规则第1条得出 Func2的时间复杂度为： O(1)

strchr执⾏的基本操作次数：

1）若要查找的字符在字符串第⼀个位置，则： T (N) = 1

2）若要查找的字符在字符串最后的⼀个位置，则： T (N) = N

3）若要查找的字符在字符串中间位置，则： T (N) =N 2

因此：strchr的时间复杂度分为：

最好情况： O(1)

最坏情况： O(N)

平均情况： O(N)

讯享网

BubbleSort执⾏的基本操作次数：

1）若数组有序，则： T (N) = N

2）若数组有序且为降序，则： T (N) = N ∗ (N + 1)/2

因此：BubbleSort的时间复杂度取最差情况为： O(N2)

外：1 2 3 4 ........ n-1 n

内：n-1 n-2 n-3 n-4 ........ 1 0

T (N) =n(n+1)/2

当n=2时，执⾏次数为1

当n=4时，执⾏次数为2

当n=16时，执⾏次数为4

假设执⾏次数为 x ，则 2x = n 因此执⾏次数： x = log n

注意课件中和书籍中 log2 n 、 log n 、 lg n 的表⽰

当n接近⽆穷⼤时，底数的⼤⼩对结果影响不⼤。因此，⼀般情况下不管底数是多少都可以省略不写，即可以表⽰为 log n

讯享网

调⽤⼀次Fac函数的时间复杂度为 O(1) ⽽在Fac函数中，存在n次递归调⽤Fac函数因此：

阶乘递归的时间复杂度为： O(n)

空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。

空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象⼤⼩差异不会很⼤，所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟实践复杂度类似，也使⽤⼤O渐进表⽰法。
注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定

函数栈帧在编译期间已经确定好了，只需要关注函数在运⾏时额外申请的空间。

BubbleSort额外申请的空间有exchange等有限个局部变量，使⽤了常数个额外空间

因此空间复杂度为 O(1)

讯享网

Fac递归调⽤了N次，额外开辟了N个函数栈帧，每个栈帧使⽤了常数个空间

因此空间复杂度为： O(N)

https://leetcode.cn/problems/rotate-array/description/

时间复杂度 O(n2)

循环K次将数组所有元素向后移动⼀位（代码不通过）

空间复杂度 O(n)

申请新数组空间，先将后k个数据放到新数组中，再将剩下的数据挪到新数组中

讯享网

空间复杂度 O(1)

• 前n-k个逆置：4 3 2 1 5 6 7

• 后k个逆置：4 3 2 1 7 6 5

• 整体逆置：5 6 7 1 2 3 4

2025年gjk算法复杂度（算法复杂度logn）

相关推荐