实验要求
采用贪心法实现:
设计原理
算法正确性证明
核心代码
void SelectCamp(double length, int n)
{
double L = 0;
int i = 0;
while (length - L > 30)
{
if ((Camp[i] - L) > 30)
{
i–;
SelectC[j] = i;
L = Camp[i];
j++;
i++;
}
else
{
i++;
}
}
}
实验结果
算法时间复杂度分析
对于while循环,在最坏的情况,也就是选择所有的宿营地的情况下,循环次数为n,在while循环中只进行了常量运算和赋值,所以每次循环是常量级时间,所以在最坏的情况下,时间复杂度为Ο(n)。
实验总结
该实验关于算法的正确性证明的关键在于,如何证明所假设的更优解的“最后一个宿营地”不是最后一个宿营地,通过观察其实是可以看出,对于更优解中每一个宿营地的选择,都不能超过贪心算法中每一个宿营地的选择范围,于是可以用数学归纳法来证明这个规律。