时间复杂度On和空间复杂度O1是什么意思？

（1）、把输入规模看成x轴，所花时间/空间看成y轴

O（n）就是y=x，y随x的增长而线性增长。也就是成正比，一条斜线。

O（1）就是y=1，是一个常量，不管x怎么变，y不变，一条与x轴平行的线。

（2）、举个简单的例子，要从0加到n，我们会这么写：

int sum = 0;

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

    sum + = i;

}

一共算了n次加法，那么就说这个时间复杂度是O（n）。当然O（n）的精确的概念是，是n的最高次方，比如，某个计算共计算了3n+2次，那么这个时间复杂度也是O（n），因为3n+2中的最高次方是n。

如果代码这么写：

int sum = 0;

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

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

               sum + = (i + j);

          }

}

很明显一共算了n^2次加法，那么就说这个时间复杂度是O（n^2），和这个上面的类似，如果某个算法计算了3*n^2+n+1次，其时间复杂度仍然是O（n^2），因为3*n^2+n+1中的最高的次方是n^2，所谓O1就是计算的次数是常量，我们还以上面从0到n的例子来说，如果我们用等差数列的公式，那么，代码可以这么写：

int sum = n*(n+1)/2

不管n有多大（当然不能溢出了），通过上面的公式只需要计算一次，也就是说计算的次数是不变的，这种情况的时间复杂度就可以说成O（1），再比如这个计算，不管其他条件如何变化，均只计算5次就能计算出结果，那么这种情况就是时间复杂度，也就是O（1）。

（3）、

要在hash表中找到一个元素就是O（1）

要在无序数组中找到一个元素就是O（n）

访问数组的第n个元素是O（1）

访问链表的第n个元素是O（n）

也就是说：

如果实现中没有循环就是O（1）

如果实现中有一个循环就是O（n）

（4）、算法复杂度：算法复杂度分为时间时间复杂度和空间复杂度。其作用是：时间复杂度是度量算法执行时间的长短；而空间复杂度是指算法所需存储空间的大小。

巴特西

时间复杂度On和空间复杂度O1是什么意思？

最新文章

热门文章