时间戳

首页 > 解决方案 > 具有常数的嵌套循环的时间复杂度

algorithm - 具有常数的嵌套循环的时间复杂度

问题描述

如果我们有一个类似下面的循环并且我们知道 c=5：

for ( int i = 0 ; i < c; i++ )
{
  // some logic
}

我们得到 O(1)。

如果我们有另一个循环：

for ( int i = 0 ; i < n; i++ )
{
  // some logic
}

我们得到 O(n),

但是如果我们有嵌套循环会发生什么：

for ( int i = 0 ; i < n; i++ )
{
   for ( int j = 0 ; j < c; j++ )
   {
     // some logic
   }

}

那会是什么时间复杂度？

标签： algorithmbig-o

解决方案

如果两者都是 O(n)，您将执行内部 O(n) n 次，给出 O(n*n) = O(n^2)。因为一个是 O(n)，另一个是 O(1)，所以你执行 O(1) n 次，得到 O(n*1) = O(n)

因此，时间复杂度为 O(n)

推荐阅读