已知输入的算法时间复杂度是什么？

Question

学习算法时，我对计算时间复杂度有一点困惑。据我理解，如果算法的输出不依赖于输入大小，则需要常量时间，即O(1)。而当输出依赖于输入时，则称为线性时间，即O(n)。

但是，当我们知道输入大小时，时间复杂度如何计算呢？

例如，我有以下代码，它打印出1到100之间的所有质数。在这种情况下，我知道输入大小（100），那么时间复杂度会如何转化呢？

public void findPrime(){

    for(int i = 2; i <=100; i++){
        boolean isPrime = true;
        for(int j = 2; j < i; j++){
            int x = i % j;
            if(x == 0)
                isPrime = false;
        }
        if (isPrime)
            System.out.println(i);
    }
}

在这种情况下，由于时间是恒定的，复杂度仍然是O(1)吗？还是应该是O(n)，其中n是影响两个循环的迭代次数的i条件？

另外，我说i的条件在运行时间方面对算法影响最大，这样说对吗？i越大，算法运行时间越长吗？

非常感谢您的帮助。

- TheTechBoss

---

输出不是动态的，总是相同的，这符合常量的定义。计算的复杂度是恒定的，它总是相同的。如果上限没有固定，那么复杂度就不会是恒定的。如果您想看证明，请告诉我。 - akuzminykh

谢谢！看到一个证明会非常有帮助，非常感谢！ - TheTechBoss

这可能是一个有点难的问题。我之前认为复杂度总是与输入相关，但实际上并非如此。因此，没有输入的算法就简单地是 *O(1)*。我也希望 findPrime() 接受一个参数 (findPrime(int max)) 并使用此参数 (i <= max)。 - MC Emperor

Answer 1

输出是静态的，始终与输入相同，这符合定义中的常数。计算复杂度是恒定的，始终如一。如果上限不固定，那么复杂度就不是恒定的。

为了引入一个动态的上限，我们需要改变代码并查看行的复杂度：

public void findPrime(int n){

    for(int i = 2; i <= n; i++){     // sum from 2 to n
        boolean isPrime = true;      // 1
        for(int j = 2; j < i; j++){  // sum from 2 to i - 1
            int x = i % j;           // 1
            if(x == 0)               // 1
                isPrime = false;     // 1
        }
        if (isPrime)                 // 1
            System.out.println(i);   // 1, see below
    }
}

随着数字 i 变得越来越长，将其打印出来的复杂度并不是恒定的。为简单起见，我们说将其输出到 System.out 是恒定的。

现在我们知道这些行的复杂度后，我们将其转化成一个方程并简化它。

由于结果是一个多项式，根据O符号的特性，我们可以看出这个函数是O(n^2)。

正如其他答案所示，你也可以通过“观察”来说它是O(n^2)。只有在更困难的情况下（并且为了确保正确性）才需要数学证明。

- akuzminykh

Answer 2

如果算法的可扩展性取决于输入大小，它不总是/必须只有 O(n²)。 它可能是 Qubic O(n³)，Logarithmic O(log₂(n)) 或其他形式。

当算法不依赖于输入大小时，也就是说，您有一定量的静态操作，这些操作不会随着输入的增长而增长-该算法被称为具有 常数时间复杂度，在渐近符号中表示为 O(1)。

通常，我们希望测量算法的最坏情况复杂度，因为这是我们对越来越大的输入感兴趣的事情（对于小输入，大多数情况下没有任何区别）。 因此，最坏情况是每个可能的迭代都将执行/发生的情况。

现在，请注意您的双重for循环。如果您在代码中具有静态范围[2,100]，当然，如果将3作为第一个质数，每次执行都将具有恒定时间复杂度O(1)，但通常，我们希望在某些动态给定的范围内找到质数，如果是这种情况，则最坏情况下，两个循环可能会遍历整个数组，并且随着数组增长-迭代次数和操作数量将增加。

因此，您的代码的最坏时间复杂度绝对是O(n^2)。

- Giorgi Tsiklauri

---

谢谢您的回复！我只是有点难以理解为什么复杂度会是O(n^2)？另外，当您说数组增长时（我猜您指的是i的条件？），我们假设它可能增长，因此计算最坏情况，对吗？ - TheTechBoss

所以，您计划保留代码中的常量2和100吗？在这种情况下，每次操作都将是恒定的数量，因为您不依赖于输入。但是我从未见过一种用于查找质数的算法，其范围是固定的。 :) - Giorgi Tsiklauri

所以这个问题是我学校作业的一部分，我需要分析代码并找出上面代码的复杂度。这就是为什么当输入已知时，我对复杂度感到如此不确定的原因。我知道我们应该计算最坏时间，但我不知道已知输入大小的情况。 - TheTechBoss

请参阅更新后的答案。如果符合您的问题，欢迎点赞并接受我的回答。但是，我建议为动态输入实现此类算法。因为每个算法（无论其有多复杂），在执行渐进分析后，都会忽略常数和低阶因素，这意味着它们始终是O(1)，因为它们不依赖于输入。 - Giorgi Tsiklauri

在你的特定情况下，它是常数时间O(1)，我已经写了 - 为什么。 - Giorgi Tsiklauri

Answer 3

当算法的时间复杂度取决于输入时，它被称为线性时间，即O(n)。但事实并非如此，当算法的时间复杂度取决于输入大小时，它只是不是常数。它可能是多项式的，这意味着它的复杂度表示为一个多项式f(n)。在这里，f(n)可以是任何带有参数n的多项式 - 例如：f(n) = n - 线性，f(n) = log(n) - 对数，f(n) = n*n - 平方等。f(n)也可以是指数，例如f(n) = 2^n，这代表一个复杂度增长非常快的算法。

- Konstantin Yovkov

Answer 4

时间复杂度取决于你使用的算法。您可以使用以下简单规则计算算法的时间复杂度：

• 基本表达式：1
• N个基本表达式：N
• 如果您有两个独立的代码块，第一个代码块的时间复杂度为A，第二个代码块的时间复杂度为B，则总时间复杂度为A + B。
• 如果您循环执行一个代码块N次，代码块的时间复杂度为M，则总时间复杂度为N * M
• 如果您使用递归函数，可以使用主定理来计算时间复杂度：https://en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms)

大O符号是一种数学符号（https://en.wikipedia.org/wiki/Big_O_notation），用于描述一个函数的上界。时间复杂度通常是输入大小的函数，因此我们可以使用大O符号来描述时间复杂度的上界。一些简单的规则：

• 常数 = O(常数) = O(1)
• n = O(n)
• n^2 = O(n^2)
• ...
• g(a*f(n)) = O(f(n))，其中 a 是一个常数。
• O(f(n) + g(n)) = O(max(f(n), g(n)))
• ...

- dangxuanvuong98