我是新手学习Java,我的问题与大O复杂度有关。
对于a),一个嵌套循环显然是O(n^2)
。
for ( int i = 0; i < n; i++)
for ( int j=0; j < n; j++ )
然而,对于 b),在结尾进行 sum++ 操作,并且在嵌套循环中存在复杂情况,这是否会改变其大O复杂度呢?
int sum = 0;
for ( int i = 1; i <= n; i++)
for ( int j = n; j > 0; j /= 2)
sum++;
get()
),这是由于库的无效假设而导致的,否则语言对于大O分析来说是无关紧要的。 - chrylis -cautiouslyoptimistic-n
值,内部循环会运行多少次。你可以看到,如果 n = 10,它将运行 4 次;对于 n = 100,它将运行 7 次;对于 n = 1000,它将运行 10 次。所以你可以看到这已经不是线性的了。然后你可以使用一些数学代数进行正式证明,但你已经知道它不应该是什么(比如 O(n^2))。 - Alexis C.