写完一个算法后呢,要评估一下,这个算法效率上跑的怎么样,一个算法衡量它最重要的标准就是它的性能如何,所以数据结构里面给出了评估它一个性能的标准,叫做: 复杂度的计算。 分下来叫:时间复杂度 和 空间复杂度。
算法效率是衡量算法运行时间和所需资源的指标。它可以用时间复杂度和空间复杂度来表示。算法效率越高,运行速度越快,所需资源越少。
算法在编写成可执行程序后,运行时需要耗费时间资源和空间(内存)资源 。 因此衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的 即时间复杂度和空间复杂度。
在计算机科学中,算法的时间复杂度是一个函数 ,它定量描述了该算法的运行时间。时间复杂度是衡量算法时间效率的指标。它表示算法运行时间与输入规模的增长关系。常见的时间复杂度有 O(1)、O(log n)、O(n)、O(n log n)、O(n²) 等。时间复杂度越低,算法效率越高。
即:找到某条基本语句与问题规模N之间的数学表达式,就是算出了该算法的时间复杂度。第一个for循环里嵌套了一个for循环,总的循环会执行NN次;
第二个for循环会执行2N次;
while循环固定 – 10 次 ;
但是,我们需要注意的是,实际我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而是只需要大概执行次数,抓大头,那么这里我们使用大O的渐进表示法。
例如:N^2+2*N+10
当 N = 10 F(N) = 130 ;
N = 100F(N) = 10210 ;
N = 1000F(N) = 1002010 ;
随着N越来越大,2N+10的值与N^2的值相比 2N+10的值太小,可以忽略,那么这里用大O渐进表示法 时间复杂度记为 O(N^2)。
Func2准确的时间复杂度是: 2N+10:这个 +10 对结果影响不大,可以忽略,省略掉。
那最后是O (2N) 还是O (N) 呢。
为什么最后取得是O (N)。
是对一个算法在运行过程中额外临时占用存储空间大小的量度。
空间复杂度不是程序占用了多少 bytes 的空间,所以空间复杂度算的是变量的个数
空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法
注意:
函数运行时所需要的栈空间(存储函数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显示申请的额外空间来确定。