lynne's blog:)

I am a force to be reckoned with.

算法之宿营地选择问题

实验要求

采用贪心法实现:

设计原理

算法正确性证明

核心代码

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)。

实验总结

该实验关于算法的正确性证明的关键在于,如何证明所假设的更优解的“最后一个宿营地”不是最后一个宿营地,通过观察其实是可以看出,对于更优解中每一个宿营地的选择,都不能超过贪心算法中每一个宿营地的选择范围,于是可以用数学归纳法来证明这个规律。

源代码:https://github.com/lynneliu-creator/algorithm
欢迎交流~