目录
1.算法的复杂度由什么衡量,如何表示?
- 衡量一个算法的好坏,一般是从时间和空间两个维度来衡量的,即时间复杂度和空间复杂度。在实际计算中,我们使用大O的渐进表示法,来近似得到一个大概的值。
2.描述一下时间复杂度:
- 时间复杂度是一个函数,它定量描述了一个算法的运行时间。而一个算法所花费的时间与其中语句的执行次数成正比例。所以一个算法中基本操作的执行次数,就为算法的时间复杂度。在实际中一般使用算法的最坏运行情况作为该算法的时间复杂度。
3.描述一下空间复杂度:
- 空间复杂度是一个数学表达式,是对一个算法在运行过程中临时占用存储空间大小的量度 。由于函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了,因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
4.O(N)和O(1)的理解:
一个未知的变量,Q(N),这个值可能很大可能很小,所以复杂度可能大小变化
一个具体的数值,O(1),这个值表示是一个固定值,复杂度是固定的
判断是Q(N)和O(1),主要还是看运行时间是否固定
5.常见算法的时间复杂度背诵:
冒泡,时间复杂度O(N^2)
二分法,时间复杂度O(long N)
斐波那契数列,时间复杂度O(2^N),递归长度为n,每次每项分裂为两项。
斐波那契数列,空间复杂度为O(N),开辟栈空间是一边开辟一边释放的,最多创建到N个,就会开始边释放边开辟,最终不会超过N个。