时间戳

首页 > 解决方案 > 如何计算嵌套“for”循环的运行时间？

algorithm - 如何计算嵌套“for”循环的运行时间？

问题描述

最近开始这样做所以需要你的帮助，假设你已经嵌套了如下所示的 for 循环，范围从 1 到 n，如何根据 Big O、Theta、Omega 计算相同的运行时间？

for(i=1; i<n; i++) {
    for(j=1; j<n; j++) {
       //some piece of code
    }
}

标签： algorithmperformancetimingnotation

解决方案

 for(i=1; i<n; i++) {
     for(j=1; j<n; j++) {
       //some piece of code
      }
  }

所以让我们仔细看看这段代码。假设我们有一组 10 个项目 (n)，我们一个接一个地执行这些循环。首先它必须通过 i 循环。他会将其传递为 1，然后该 1 在 1 变为 2 之前进入第二个循环 10 次。总共它必须通过循环 100 次才能到达终点。在大 O 表示法中，我们总是为最坏的情况计算 O。也就是说，需要一个位于循环末尾的项目。假设我们将 1 添加到 n。现在它必须通过循环多少次？11 * 11 即 121。因此，每当您的输入增长 1 时，该算法的成本就会呈指数增长。这就是为什么我们说 O(n^2)。

推荐阅读