更改其索引的单个循环的复杂性
Complexity of single loop that changes its index
有人可以解释一下如何评估以下代码的复杂性吗？考虑 array_of_size_n 由升序排列的正随机数组成。
for(i = 0; i < n; i++){
temp = array_of_size_n[i] + last
if(temp > last){
do_something_else(temp); //doesn't change the complexity
last = temp;
i = 0;
}
}
根据我的测试，增长是线性的，有一个很大的常数因子。
假设一开始 last 为 0。
它总是传递第一个值，因为循环中的 i++ 。
所以当涉及到第二个值时，如果是1，那么last会加到INT_MAX。那么 if(temp > last) 将永远为假，因此是线性的。
第二个值的大小将影响最后到达 INT_MAX.
的速度
有人可以解释一下如何评估以下代码的复杂性吗？考虑 array_of_size_n 由升序排列的正随机数组成。
for(i = 0; i < n; i++){
temp = array_of_size_n[i] + last
if(temp > last){
do_something_else(temp); //doesn't change the complexity
last = temp;
i = 0;
}
}
根据我的测试，增长是线性的，有一个很大的常数因子。 假设一开始 last 为 0。 它总是传递第一个值，因为循环中的 i++ 。 所以当涉及到第二个值时，如果是1，那么last会加到INT_MAX。那么 if(temp > last) 将永远为假，因此是线性的。 第二个值的大小将影响最后到达 INT_MAX.
的速度