algorithm - 复杂算法分析

Question

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

例如，我为我正在开发的程序编写了这个 Python 算法，以从文件中读取所有字节，并使用分隔数据的 4 字节标签将它们分成 block 。每个标签都以“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)。

我如何针对包含整个算法(而不仅仅是部分)的最坏情况进行分析？

Answer 1

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

1. 请记住，只有最主要的被加数才是重要的，可以忽略常数因素。
2. 从内到外分析循环。

所以步骤是:

• 前 4 行都在 O(n) 中。
• while 循环的内部是 O(1+k) = O(k):
  • in tags 在 O(t) 中，t 是已知标签的数量。由于该数字与 n 无关，因此与 O(1) 相同。
  • tagIndexes += [i] 在 O(1) 中 [source]
  • 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] 访问列表的最后一个元素。