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

Question

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

我不太擅长分析算法的时间，但我知道这个算法中的 while 循环应该花费最多的时间。在本例中，程序从左到右查看字符串中的每个字符:

while pos <= last :

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

但是，该算法在该循环内有很多“if”和“elif”语句；我不知道他们是否会显着影响时间。谁能帮我解决这个问题？我想通过总结来计算时间效率。

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

谢谢!

Answer 1

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

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

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

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