数据结构 第一节 第三课
【摘要】
[toc]
最坏时间复杂程度
分析算法时, 存在几种可能的考虑:
1. 算法完成工作最少需要多少基本操作, 即最优时间复杂度
2. 算法完成工作最多需要多少基本操作, 即最坏时间复杂度
3. 算法完成工作平均需要多少基本操作, 即平均时间复杂度
对于最优时间复杂度, 其价值不大, 因为它没有提供什么有用信息, 其反映的只是最...
[toc]
最坏时间复杂程度
分析算法时, 存在几种可能的考虑:
1. 算法完成工作最少需要多少基本操作, 即最优时间复杂度
2. 算法完成工作最多需要多少基本操作, 即最坏时间复杂度
3. 算法完成工作平均需要多少基本操作, 即平均时间复杂度
对于最优时间复杂度, 其价值不大, 因为它没有提供什么有用信息, 其反映的只是最乐观最理想的情况, 没有参考价值.
对于最坏时间复杂度, 提供了一种保证, 表明算法在此种程度的基本操作中一定能完成工作.
对于平均时间复杂度, 是对算法的一个全面评价, 因此它完整全面的反映了这个算法的性质. 但另一方面, 这种衡量量并没有保证, 不是每个计算都能在这个基本操作内完成, 而且, 对于平均情况的计算, 也会因为应用算法的实例分布可能不均匀而难以计算.
因此, 我们主要关注算法的最坏情况, 亦即最坏时间复杂度.
时间复杂度的几条基本计算规则
1. 基本操作, 即只有常数项, 认为其其时间复杂度为 O(1)
2. 顺序结构, 时间复杂度按加法进行计算
3. 循环结构, 时间复杂度按乘法进行计算
4. 分支结构, 时间复杂度取最大值
5. 判断一个算法效率时, 往往只需要关注操作数量的最高次项, 其它次要项和常数项科研忽略
6. 在没有特殊说明时, 我们所分析的算法的时间复杂度都是指最坏时间复杂度
文章来源: iamarookie.blog.csdn.net，作者：我是小白呀，版权归原作者所有，如需转载，请联系作者。
原文链接：iamarookie.blog.csdn.net/article/details/109173354
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
评论（0）