《数据结构和算法之美》学习条记 Day 2

源代码 · 2024-9-19 05:12:46

课程：《复杂度分析（上）：怎样分析、统盘算法的实行服从和资源斲丧？》总结

算法的一个非常重要的的考量指标是实行服从，复杂度分析就是用来权衡代码实行服从的一种方法。前面又提到复杂度分析是数据结果和算法学习的精华。
为什么必要复杂度分析？

1. 现实的测试结果非常依靠测试环境
好比测试环境硬件配置不一样，得到的结果大相径庭
2. 测试结果受数据规模的影响很大
好比排序算法，就会受现实测试数据的有序度和数据的规模影响。导致测试的结果无法反应算法的性能。
3. 可以开辟阶段更好的引导代码的编写
复杂度分析可以估算代码的实行服从，从而在根据现实选择算法时起到肯定的引导作用。
复杂度分析不必要详细测试数据测试，就可以大概估盘算法实行服从。既快速方便，又不受测试环境的影响，所以我们必要复杂度分析。
复杂度分析包括时间复杂度分析和空间复杂度分析，那么怎样举行复杂度分析呢？
大O复杂度表现法

如果我们将每行代码的实行时间当作固定的，那全部代码的实行时间 T(n) 与每行代码的实行次数成正比。我们再将每行代码的实行次数之和用f (n)表现，那就可以总结出一个公式:
T(n) = O(f(n))
此中n表现数据规模的巨细，O代表T(n)与f(n)之间是正比关系。这就是大O时间复杂度表现法。
大O时间复杂度表现的是代码实行时间随数据规模增长的变革趋势。并不是正真的实行时间。当n很大时，公式中的低阶、常量、系数三部分对变革趋势影响不大，所以可以忽略，只记载最大量级的谁人就可以了。
时间复杂度分析

三个实用的时间复杂度分析方法:

1. 单一循环看次数实行最多的
2. 如果代码只受单一数据规模n的影响，非嵌套循环相加取量级最大的
3. 如果代码受多个数据规模的影响，非嵌套循环相加取和

4. 嵌套循环表里相乘取乘积

常见的时间复杂度有：<b>O(1)、O(logn)、O(n)、O(nlogn)、O(

《数据结构和算法之美》学习条记 Day 2

所属分类: 问答交流

新帖推荐: 30日

推荐作品