java - 输入已知的算法的时间复杂度？

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 是影响两个 for 循环的迭代次数的 i 条件？

我是否也正确地说 i 的条件在运行时间方面对算法的影响最大？i越大，算法运行的时间越长？

将不胜感激任何帮助。

标签： javaalgorithmtime-complexity

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) 。您只需要针对更困难的情况（并且可以肯定）进行数学证明。