固定循环的大 O

Question

我在面试期间讨论了一些代码，我认为我没有很好地阐明我的代码块之一。

我知道（高级）我们被教导了两个 for 循环 == O(n^2)，但是当您将某些断言作为工作的一部分将完成的工作限制为恒定数量时会发生什么。

我想出的代码是这样的

String[] someVal = new String[]{'a','b','c','d'} ;// this was really - some other computation
if(someVal != 4) {
  return false;
}

for(int i=0; i < someVal; i++){
  String subString = someVal[i];
  if(subString.length() != 8){
    return false;
  }
  for(int j = 0; j < subString.length(); j++){
    // do some other stuff
  }
}

所以有两个for循环，但是由于在继续之前进行长度检查，迭代次数变得固定。

for(int i=0; i < **4**; i++){
  String subString = someVal[i];
  if(subString.length() != 8){ return false }

  for(int j = 0; j < **8**; j++){
    // do some other stuff
  }
}

我试图争辩说这使它保持不变，但没有做得很好。我是完全错误还是离题了？

Answer 1

for 循环内部的早期退出条件是 if(subString.length() != 8)，因此如果长度恰好为 8，则随时执行第二个 for 循环。这实际上使第二个 for 循环的复杂度保持不变，因为它不取决于输入大小。但是在您的第一个 for 循环之前，您有另一个提前退出条件 if(someVal != 4) 使第一个 for 循环也保持不变。

所以是的，我会遵循你的论点，即完整的函数具有恒定的大 O 时间复杂度。也许在解释中重复 big-O 总是描述一个 upper 边界复杂度，它永远不会被跨越并且常数时间因子可以减少到 1.

但请记住，基于真实世界输入的恒定复杂度在执行时间上仍可能比基于 n 的大小的 O(n) 复杂度更长。如果这是一个已知的前提条件 n 不会超过（低）给定数字，我不会争论 Big-O 复杂性，而是争论整体预期运行时间，其中循环的第二个常量可以比 Big-O 复杂性分析的预期影响更大。

固定循环的大 O

Big-O of fixed loops

big-o

time-complexity