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

我说 i 的条件对算法的运行时间影响最大​​，我说得对吗？ i 越大，算法运行的时间越长？

非常感谢任何帮助。

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 是常量。

现在，当我们知道线条的复杂性时，我们会将其转化为方程式并对其进行简化。

由于 properties，结果是一个多项式的O 表示法，我们可以看到这个函数是O(n^2)。

如其他答案所示，您也可以通过“锁定它”说它是 O(n^2)。只有在更困难的情况下(并且可以肯定)，您才需要数学证明。