0

所以，在我的数据结构课上，我们最近学习了算法分析和 Big-O 分析。到目前为止，我们实际上只将其应用于排序算法，分析起来相对简单。我很好奇如何分析更复杂的算法。

例如，我为我正在编写的程序编写了这个 python 算法，用于从文件中读取所有字节，并使用分隔数据的 4 字节标签将它们分成块。每个标签都以“h”开头，我有一个单独的可能标签列表，用于确定 4 字节序列是否为标签。算法定义如下

data = file.read()
blocks = []
tagIndexes = []
i = data.index(b'h')
try:
    while 1:
        if data[i:i+4] in tags:
            tagIndexes += [i]
        i = data.index(b'h', i+1)
except ValueError:
    pass
for j in range(len(tagIndexes) - 1):
    index = tagIndexes[j]
    nextIndex = tagIndexes[j+1]
    blocks += [block(data[index:index+4], data[index+4:nextIndex])]
lastIndex = tagIndexes[len(tagIndexes) - 1]
blocks += [block(data[lastIndex:lastIndex+4], data[lastIndex+4:])]
return blocks

我不是在询问有关如何改进算法的评论。如果以后有必要，我可以自己做。我的问题是如何确定该算法的最坏情况或 Big-O 表示法。其中有几个子算法，对于大多数较小的算法，很容易看到最坏的情况。例如，python 的 list.index(val) 方法的最坏情况是如果列表中没有指定的值，在这种情况下，它只会循环整个事物并引发错误 O(n)。但是，围绕该方法循环的最坏情况是，如果每个字节都是“h”O(n)。但在这种情况下，对 data.index() 的每次调用都会非常快并立即返回 O(1) 值。然后第二个循环的最坏情况是如果每 4 个字节是一个标记 O(n/4)。

对于包含整个算法的最坏情况，我该如何分析，而不仅仅是部分？

4

2 回答 2

2

此分析的两个最重要的提示是：

  1. 请记住，只有最主要的总和很重要，并且可以忽略常数因素。
  2. 从内到外分析循环。

所以步骤是：

  • 前 4 行都在O(n).
  • while 循环的内部位于O(1+k) = O(k)：
    • in tags与已知标签O(t)的t数量有关。由于该数字与 无关n，因此与 相同O(1)。
    • tagIndexes += [i]在O(1) [来源]
    • data.index()是O(k)，k是输入数据中标签的平均距离
  • 循环迭代次数为n/k。现在，您将迭代次数与一次迭代的成本相乘，您就有O(n)了第一个循环。
  • for循环的内部在O(k)（假设block(a,b)是O(len(a)+len(b))）：
    • 前两个索引访问是O(1)
    • data[index+4:nextIndex]是O(k-4) = O(k)。block(...)也是O(k)。那实际上是 2 k，但由于我们可以忽略常数因素，所以整行是O(k)。
  • 循环再次运行n/k时间，所以它也在O(n).

因此，算法的总时间O(n)再次成为常数因子，所有较小的和被忽略。

希望对您有所帮助——如果您有任何问题，请发表评论。

除此之外，这里有两个与代码样式相关的小指针：

  • 是while True，不是while 1。
  • list[-1]您通过而不是访问列表的最后一个元素list[len(list)-1]。
于 2013-09-19T00:07:52.593 回答
1

您已经意识到，虽然为算法的每个部分找到最坏的情况相对容易，但它们有时有些不兼容，即它们不能一起发生。但最坏情况分析并不关心这一点。它的目的是给你一个运行时间/空间使用的上限，所以如果你最终得到的界限太糟糕以至于它永远不会发生，那也没关系。我们总是对尽可能紧密的界限感兴趣，但有时没有可以通过直接方法证明的真正紧密的界限；在这些情况下，分析结果往往比算法实际执行的更糟糕，这就是为什么最坏情况分析通常被称为“悲观”方法的原因。

为了解决最坏情况边界没有像我们希望的那样严格的问题，您可以尝试几种方法：有摊销分析，它处理操作序列的成本，它有时会给出更严格的边界比只看一个操作；有概率分析，它使用概率来查看需要完成昂贵工作的频率是否有助于降低预期的运行时间/空间使用；还有平均案例分析，它基本上是概率分析，您假设所有可能的输入具有相同的概率。这三种方法根据手头的算法有不同的难度，并且倾向于用于更高级的算法和数据结构，因为那些通常不会'

所以总结一下：最坏情况分析并不总是会给你严格的界限，这就是为什么它有时被称为悲观。您可以使用其他分析技术来尝试获得更严格的界限，但即使这些也并不总是有帮助。鉴于您刚刚开始使用算法及其分析，我非常怀疑您以前是否听说过这些技术，更不用说应用它们了，所以进行最坏情况分析是非常好的，不用担心结果不是紧密结合。

于 2013-09-19T00:06:12.397 回答