算法面试中时间复杂度和空间复杂度 o(n) o(logn) 是什么？

我会带着你远行 2023-06-30 02:46 3阅读 0赞

算法面试中 时间复杂度和空间复杂度 o(n) o(logn) 是什么？

面试中经常问的各类算法，比如冒泡算法，堆排序算法，大家可以多关注我们语音分享，都有相关分析，不过还会遇到问是时间复杂度和空间复杂度O（n^2），O（1），这些是什么，一个算法的优劣主要从算法的所需时间和所占用的空间两个方面衡量。

什么是时间复杂度：

int x=1;

while (x <n)

x++;

该算法执行次数是如果n=10, 执行次数就是10，n是个变量，用时间复杂度表示是O(n)。大O符号是数学表达式，表示一个界限。

如果两层循环

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

//… \}

该算法for循环，最外层循环每执行一次，内层循环都要执行n次，执行次数是根据n所决定的，最大时间复杂度是O（n^2），如果内层循环在某种场景一次就跳出,其实也可以退化成o(n), 通常我们计算时间复杂度都是计算最多情况.由此类推，如果是三层循环，最大时间复杂度就是 O（n^3）

什么是空间复杂度，我们说程序运行起来都需要占内存，空间复杂度就是一个算法所需内存大小

例如冒泡排序

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RvbnlfMzI4NDI3Njg1_size_16_color_FFFFFF_t_70]

两层循环，最大时间复杂O（n^2），最小时间复杂O（n），内部交换只需要一个变量，所以空间复杂度O(1)

现在我们可以对主要常见算法做个汇总说明，出现Log指数级别的一般是递归，简单说自己调用自己  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RvbnlfMzI4NDI3Njg1_size_16_color_FFFFFF_t_70 1]

算法稳定性什么意思？如果排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同，我们说算法具有稳定性，有什么意义呢？如果排序的算法是稳定的，第一个次排序的结果和关键字段可以为第二个次排序所用。上面给出的冒泡排序就是这样。

最后，算法和性能的关系，衡量一个算法的好坏，主要通过数据量大小来评估时间和空间，这些最后都直接会影响到程序性能，一般空间利用率小的，所需时间相对较长。所以性能优化策略里面经常听到 空间换时间，时间换空间这样说法。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RvbnlfMzI4NDI3Njg1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200114172339661.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RvbnlfMzI4NDI3Njg1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RvbnlfMzI4NDI3Njg1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200114172354540.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RvbnlfMzI4NDI3Njg1,size_16,color_FFFFFF,t_70