python - 双变音位算法的最佳/最差/平均时间效率是多少？

Question

我正在研究双变音算法。我只想计算算法所属的效率等级。这是在Python中。这是我能找到的最易读的代码。

我不是很擅长分析算法的时间，但我知道这个算法中的 while 循环应该花费最多的时间。在这种情况下，程序从左到右查看字符串中的每个字符：

while pos <= last :

我假设这将需要 n 步，其中 n 是字符串的长度。

然而，该算法在这个循环中有很多“if”和“elif”语句；我不知道它们是否会显着影响时间。谁能帮我完成这个？我想通过总结来计算时间效率。

为了尝试回答我自己的问题，我认为它的最佳效率是长度为 1 的字符串，它必须输入尽可能少的“if”语句。另一方面，最坏的情况可能只是一个非常长的字符串。

谢谢！

Answer 1

在不考虑每个条件的情况下，这对我来说是线性的。下面有一些例外的简单规则是 if/then 语句不会影响算法的渐近运行时，除非它们执行某种循环或递归。我看到的一切看起来都像是常数时间运算。

如果我真的需要确定，这就是我将如何处理它。如果它不是直接依赖于条件语句，你需要寻找一些东西

1. break语句和其他改变控制流的东西——这可能会减少渐近时间
2. whileor语句中变量的不规则修改for，这可能会使算法花费更多时间。在这里，这意味着要么要么pos被last修改。

这不是一个完整的列表，但它可能会对您有所帮助。