时间戳

首页 > 解决方案 > 我如何计算这个算法的时间复杂度？

time - 我如何计算这个算法的时间复杂度？

问题描述

我一直在尝试计算这个算法的时间复杂度，但我认为我是对的。

由于它不能是 n^2，所以我想出了一个 O(n*(j*(1+j)*50) 的公式，但我仍然不确定。

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i ; j++)
        for (int k = 1; k <= 100; k++)
           cout << "Hello";

任何帮助，将不胜感激。

标签： timecomplexity-theory

解决方案

这O(n²)确实是。内循环以恒定时间运行。它与

for(int i = 1;i<=n;i++)
  for(int j = 1;j<=i;j++) {
      cout << "Hello";
      cout << "Hello";
      cout << "Hello";
      cout << "Hello";
      /* repeats 96 mores times */
  }

更具体地说，您可以将步数计算为

T(n) = 1 + 2 + 3 + ... + n
     = n * n(1 + n)/2
     = (n² + n)/2

常量无关紧要，所以这个函数在O(n² + n)简单的地方增长O(n²)。

您可以将所有内容乘以 100，而不是展开内部循环，但这不会改变复杂性。

推荐阅读