Java算法中的大O符号

Question

我对这个大 O 符号问题感到困惑。这段代码看起来不像O(n) 但是for loop turns number of word time 所以基本上不超过20 所以，如果我们说 Length (line.split()) 是常量 c，我们可以说 O(c.n) = O(n) 吗？

while (this.scannerMainText.hasNextLine()){
        String line = this.scannerMainText.nextLine();
        for (String word : line.split("[.!,\" ]+")) {
           some statements
         }
     }

Answer 1

是的。

时间复杂度仅基于算法的次数运行；算法中的实际 number/cost 步（c，如您所说）不考虑用于 Big-O 表示法。

已添加

我对理论的边缘情况不够熟悉，无法说如果所有线的长度都相等，您可以将内部循环的运行时间减少到一个常数。 一般来说，这个算法会被认为是 O(mn)。

Answer 2

是的，一个循环的次数运行对持续时间的影响可以忽略不计，因此通常不会在 Big-O 表示法中提及。

例如，如果一个 O(n) 循环是运行 20 次，你会认为符号是 O(20n)，但是因为影响很小所以没有提到它 Big -O 表示法，因此 O(20n) = O(n)。 O(20n²) = O(n²) 等也是如此..

Java算法中的大O符号

Java Big O notation in algorithm

java

big-o