时间复杂度与空间复杂度

开发者 · 2024-9-9 03:20:40

时间复杂度是指步伐运行从开始到竣事所须要的时间。通常分析时间复杂度的方法是从算法中选取一种对于所研究的标题来说是根本运算的利用，以该利用重复实行的次数作为算法的时间度量。一样平常来说，算法中原利用重复实行的次数是规模n的某个函数T(n)。由于许多情况下要准确计算T(n)是困难的，因此引入了渐进时间复杂度在数目上估计一个算法的实行时间。其界说如下：
假如存在两个常数c和m，对于全部的n，当n≥m时有f(n)≤cg(n)，则有f(n)=O(g(n))。也就是说，随着n的增大，f(n)渐进地不大于g(n)。比方，一个步伐的现实实行时间为T(n)=3n3+2n2+n，则T(n)=O(n3)。
常见的对算法实行所需时间的度量：

2、常见算法逻辑的时间复杂度：
（1）单个语句，或步伐无循环和复杂函数调用：O(1)
（2）单层循环：O(n)；双层嵌套循环：O(n2)；三层嵌套循环：O(n3)。
（3）树形布局、二分法、构建堆过程：O(log2n)。（4）堆排序、归并排序：O(nlog2n)。
（5）全部差别可能的分列组合：O(2n)

时间复杂度与空间复杂度

所属分类: 问答交流

新帖推荐: 30日

推荐作品