algorithm - 算法时间复杂度的输入单元

Question

在大多数在线资料中，只要输入“n”，您就可以计算出符号的大“O”。但是，网上有讲座将“位数”作为输入。使用“位”作为输入来查找算法的 Big-O Omega 和 theta 是什么意思？

Answer 1

您可以将大 O 表示法当作一种语言来表达复杂性。通常你首先想到哪些参数影响算法，然后你估计这个影响，最后你用 Big-O 的通用语言表达它。

作为输入的位:理论上，如果输入的整数大小差异很大，您想展示它如何影响您的算法。

作为输入的实例数:另一方面，忽略位数实际上是有道理的。例如，如果我们处理整数，那么大多数操作需要多达几个处理器周期，并且它不取决于这个整数有多大，只要它适合 32 位或 64 位。它不太精确且更抽象，但在大多数情况下，这就是您真正想要的。

这完全取决于算法的复杂性从何而来，你想强调什么。

在某些情况下它确实很重要的示例:

想象一个平衡的 BST。众所周知，search 需要 O(log n)。如果您有非常长的整数(k 位)，那么逐位比较，您会得到 O(k log n) 算法。但是，使用简洁的数据结构，您可以尝试实现 O(log kn)。 [通过将整数切割成碎片并使用类似 Trie 的东西]