该代码的时间复杂性是什么？

发布于 2025-02-06 20:50:49 字数 1218 浏览 1 评论 0原文

我正在学习考试，我遇到了这段代码，我需要找到最好和最坏的情况。

  A(n):
  for (int i = 1; i < n; i*=2) {
     for (int j = 0; j < i; j++) {
        if (i == j) return; // does nothing
        for (int k = n; k > 0; k--)
           if (f(n)) 
              return g(n);
     }
  }

最坏的功能和最佳情况是：

f（n）o（n）ω（log^7（n））

g（n）o（n^2 * log^6（n））ω（n^2 * log^6（n））

最坏情况： 第一个循环的复杂性是log（n），第二个循环取决于第一个循环，但我会说它的复杂性是n。循环的第三个是n。 f（n）在O（n）中检查，在最坏的情况下g（n）将在上次迭代中执行，其复杂性为o（n^2 * log log ^6（n））。所以我想说最坏的情况是log（n） * n * n * n + n^2 * log^6（n），所以它是 o（n^3 * log（n）） 。

另一个逻辑是，由于第二个循环取决于第一个循环，因此迭代将进行1 + 2 + 4 + 8 + 8 + 16 ...是几何序列，其值是2 ^log（n）是n。第一个循环下的一切都将保持不变，因此在这种情况下，big-o将是 o（n^3）

最佳案例：我发现最好的情况是（n^2 * log^6（n）），因为它将直接返回语句，而无需迭代。

基本上，主要问题是log（n）执行的循环如何影响嵌套n times times times已执行的循环，这取决于它。哪种逻辑适合最坏情况，最好的情况还可以吗？

原文

I'm studying for exam and I came across this piece of code and I need to find best and worst case.

  A(n):
  for (int i = 1; i < n; i*=2) {
     for (int j = 0; j < i; j++) {
        if (i == j) return; // does nothing
        for (int k = n; k > 0; k--)
           if (f(n)) 
              return g(n);
     }
  }

whereas functions worst and best cases are:

f(n) O(n) Ω(log^7(n))

g(n) O(n^2 * log^6(n)) Ω(n^2 * log^6(n))

Worst case:
Complexity of the first loop is log(n), and the second loop depends on first but I would say that it's complexity is n. Third for loop is n. f(n) is checked in O(n) and in worst case g(n) will be executed in last iteration and it's complexity is O(n^2 * log^6(n)). So I would say that worst case is log(n) * n * n * n + n^2 * log^6(n), so it's O(n^3 * log(n)).

Other logic would be, that as second loop depends on the first one, the iterations will go 1 + 2 + 4 + 8 + 16... which is geometric series and it's value is 2^log(n) which is n. Everything under first loop would stay same, so in this case Big-O would be O(n^3)

Best case: I found that the best case would be (n^2 * log^6(n)) as it would go straight to return statement without iterating at all.

Basically, the main question is how does log(n) times executed loop affects nested n times executed loop which depends on it.
Which logic is right for worst case, and is the best case ok?

分享到QQ

分享到微博