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

科技前沿 • 2025-04-28 15:56 • 阅读 41

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

一、

什么是数据结构：

在内存当中管理数据。

算法复杂度：时间和空间

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

时间复杂度：一个算法运行之中的次数（函数调用、循环），类似于数学中的函数式。

实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要 大概执行次数，那么这里我们使用大 O 的渐进表示法。O（）

法则：

1.保留最高阶项，将小一个量级的全舍弃（比如N*logN+N要舍弃N，变成N*logN）

2.同阶全保留

3.O（1）表示常数次，而不是1次

4.同阶系数忽略掉，2*N 变成O（N）（当一次程序需要两个N才能执行完时，时间复杂时O（N），不是2*N）

5.不确定次数的算法，按最坏情况O（N）确定算法复杂度了（ M+N次，有两个未知数M和N，时间复杂度为 O(N+M) ）

6.计算循环（循环几次）和递归（调用几次）次数，不考虑其他

常见阶数：

常数、线性、平方、立方、次方、对数、N*logN、指数函数阶

//暴力查找O（N）；冒泡排序  O(N*N)； qsort O(N log2N) ;   二分查找 O(Log2N)

 

 

空间复杂度：

也是一个数学表达式，也用！!O渐进表示法! !。

计算量：

1.额外开辟的数组、变量、动态内存、函数等空间

2.形参不算

3.函数运行时所需要的栈空间 ( 存储参数、局部变量、一些寄存器信息等 ) 在编译期间已经确定好了，因

此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定

4.栈帧的计算

long long Fac ( size_t N )

{

if ( N == 0 )

return 1 ;

return Fac ( N - 1 ) N ;

}

递归调用了 N 次，开辟了 N 个栈帧，每个栈帧使用了常数个空间（如：寄存器等….（但是由于是常数个·都可以不算进去））。空间复杂度为 O(N)

斐波那契数列的空间复杂度：空间O（N）

原因：

讯享网

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

相关推荐