最佳和最坏情况 - 时间复杂度
Best and worst case - Time compexity
我必须找到算法的最佳和最坏情况，但我不明白结果：
int chOne=1;
for (int i=0; i<list.lenght; i++)
if(list[i]<list[chOne]){
chOne=i;
}
return chOne;
BC:2c+2c(n-1)=2cn
WC:2c+3c(n-1)=3cn-c
不知道什么是"n-1"；并按照其他类似的练习，它会是（我认为）
BC:5c
WC:3c+2cn
有人能告诉我为什么不是这样吗？
谢谢！
精确的数字取决于您认为算法模型中的原子操作。
然而，它始终认为
- 访问整个列表，增加当前索引
i，测试循环终止并在每次迭代中检查新的最小值。
- 只要当前访问的列表元素小于
chOne 索引的当前最小候选元素，就会发生更新操作。
所以你最好的情况是，当没有更新发生时（如果初始选择 chOne 索引最小的列表元素就是这种情况）并且在最坏的情况下每次迭代都会发生更新但是1，后者是当前列表索引等于chOne原选择时的迭代（要么已经有更新，那么当前索引的元素不能小于当前选择，要么原索引chocie有是 0，那么两个索引是相同的）。
用n表示列表长度，2c是每次迭代的固定成本和c一次chOne更新的成本，你有1次迭代保证花费 2c 和 n-1 次迭代，每次迭代至少花费 2c 并且可能 3c.
我必须找到算法的最佳和最坏情况，但我不明白结果：
int chOne=1;
for (int i=0; i<list.lenght; i++)
if(list[i]<list[chOne]){
chOne=i;
}
return chOne;
BC:2c+2c(n-1)=2cn
WC:2c+3c(n-1)=3cn-c
不知道什么是"n-1"；并按照其他类似的练习，它会是（我认为）
BC:5c
WC:3c+2cn
有人能告诉我为什么不是这样吗？ 谢谢！
精确的数字取决于您认为算法模型中的原子操作。
然而，它始终认为
- 访问整个列表，增加当前索引
i，测试循环终止并在每次迭代中检查新的最小值。 - 只要当前访问的列表元素小于
chOne索引的当前最小候选元素，就会发生更新操作。
所以你最好的情况是，当没有更新发生时（如果初始选择 chOne 索引最小的列表元素就是这种情况）并且在最坏的情况下每次迭代都会发生更新但是1，后者是当前列表索引等于chOne原选择时的迭代（要么已经有更新，那么当前索引的元素不能小于当前选择，要么原索引chocie有是 0，那么两个索引是相同的）。
用n表示列表长度，2c是每次迭代的固定成本和c一次chOne更新的成本，你有1次迭代保证花费 2c 和 n-1 次迭代，每次迭代至少花费 2c 并且可能 3c.