时间戳

首页 > 解决方案 > 固定循环的大 O

time-complexity - 固定循环的大 O

问题描述

我在一次采访中讨论了一些代码，但我认为我没有很好地阐明我的一个代码块。

我知道（高级）我们学习了两个 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
  }
}

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

标签： time-complexitybig-o

解决方案

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

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

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

推荐阅读