空循环的大O [英] Big O of empty loops

问题描述

如果我有这样的循环结构

If I have a loop construction like this

for(int i=1; i<n;i++)
   for(int j=1; j<n;j++);

O(n ² )或O(0)?

O(n²) or O(0)?

假定循环内是一个if:

Assume that inside the loop is an if:

for(int i=1; i<n;i++)
   for(int j=1; j<n;j++)
      if(a==b) do();

我想知道最好和最坏的情况，假设do()为O(1).

and I want to know best and worst case, assuming do() is O(1).

最差:如果语句始终为真，则O(n ² )

Worst: O(n²) if statement always true

最佳:如果语句始终为假，则为O(0)

Best: O(0) if statement always false

对吗?

推荐答案

在我们的上下文中，没有O(0)这样的东西；有效地是恒定时间(O(1))，如果优化掉了.

There's no such thing as O(0), in our context; it'd be effectively constant-time (O(1)), if optimized away.

关于这种情况，不.如所写，它仍然是O(N ^嵌套循环数).优化器可能会完全删除代码，但最坏的情况"是代码没有删除，并且CPU运转不顺.通过这些循环.

As for whether that's the case, no. As written, it's still O(N^number of nested loops). An optimizer might remove the code entirely, but the "worst case" is that it doesn't, and the CPU's spinning its wheels. through those loops.

这篇关于空循环的大O的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！