4

我一直在申请工作，每次听到有关算法时间/空间复杂性的问题时，我都会畏缩和跌跌撞撞。无论我读了多少书，我的大脑似乎都被编程为无法获得任何东西，我认为原因是因为逃学导致我的数学背景非常低。这可能不是常见的 SO 问题，甚至可能由于从根本上讲数学而被删除，但至少我希望我能弄清楚这个问题接下来要去哪里。

4

3 回答 3

8

我不知道为什么工作的人会这样做，所以这里只是几个例子。整个“复杂性”只是提供算法使用多少时间（或内存）的指示。

现在，如果您有一个包含值的数组，则访问给定索引处的值是 O(1) - 常量。in 数组有多少元素并不重要，如果您有索引，则可以直接获取该元素。

另一方面，如果您正在寻找一个特定的值，您将别无选择，只能查看每个元素（至少在找到一个元素之前，但这对于复杂性无关紧要）。因此，在随机数组中搜索是 O(n)：运行时间对应于元素的数量。

另一方面，如果您已经对数组进行了排序，那么您可以进行“二分搜索”，即 O(log n)。“Log n”是二进制对数，基本上是 2^n 的倒数。例如，2^10 是 2*2*2*2...*2 10 次 = 1024，而 log2(1024) 是 10。因此，通常认为 O(log n) 的算法非常好：找到一个使用二进制搜索排序数组中的元素，如果数组最多有 1024 个元素，则二进制搜索只需查看其中的 10 个即可找到任何值。对于 1025-2048 元素，它最多为 11 次，对于 2049-4096 则为 12 次，依此类推。因此，添加更多元素只会慢慢增加运行时间。

当然，事情可能会变得更糟。一个简单的排序算法往往是 O(n**2)，这意味着对于只有 2 个元素的数组，它需要 2^2 = 4 次“操作”，如果数组有 3，则需要 3^2 = 9，4^2 =如果数组有 4 个元素，则为 16，依此类推。实际上很糟糕，考虑到只有 1000 个元素的数组已经需要 1000*1000 = 100 万次比较才能排序。这被称为指数增长，当然它可能会变得更糟：O(n^3)、O(n^4) 等。越来越糟糕。

一个“好的”排序算法是 O(n*log n)。假设一个数组有 1024 个元素，这将是 1024*10=10240 比较 --- 比我们之前的 100 万要好得多。

只需将这些 O(...) 作为运行时行为（或应用到内存时的内存占用）的指标。我确实插入了实数，你可以看到数字是如何变化的，但这些并不重要，通常这些复杂性是最坏的情况。尽管如此，仅看数字，“恒定时间”显然是最好的，指数总是不好的，因为运行时间（或内存使用）飞速增长。

编辑：另外，你对常数因素并不感兴趣；您通常不会看到“O(2n)”。这仍然是“O(n)”——运行时与元素的数量直接相关。

于 2012-08-19T13:56:18.257 回答
7

要分析算法的时间/空间复杂度 - 高中知识应该没问题。我在大学学过这个。在我的第一个学期，我很好。

基础的兴趣领域是：

以上对于分析算法的复杂性是正确的。计算问题的复杂性是一个更深层次的领域，仍处于研究阶段——复杂性理论。这需要广泛的集合论、计算理论、高级微积分、线性代数等知识。

于 2012-08-19T13:46:12.307 回答
5

虽然了解微积分、求和级数和离散数学都是好事，但从您的问题和我在行业中的有限经验来看，我怀疑您的面试官是否期望达到这种理解水平。

在实践中，您可以对时间和空间复杂性做出有用的大 O 语句，而无需进行大量的数学思考。以下是基础知识，我将根据时间复杂度来讨论这些基础知识，只是让语言不那么抽象。

大 O 时间复杂度告诉您算法的最坏情况运行时间如何随其输入的大小而变化。您从 big-O 函数获得的实​​际数字表示您的算法将在给定大小的输入上执行的恒定时间操作的数量。

因此，big-O 函数只计算您的算法将执行的恒定时间操作的数量。

  • 恒定时间操作称为 O(1)。[请注意，任何固定长度的恒定时间操作序列也是 O(1)，因为该序列也需要恒定的时间。]

O(k) = O(1)，对于任何常数 k。

  • 如果您的算法连续执行多个操作，则将它们的成本相加。

O(f) + O(g) = O(f + g)

  • 如果您的算法多次执行操作，则将操作的成本乘以执行的次数。

n * O(f) = O(n * f)

O(f) * O(f) * ... * O(f) = O(f^n)，其中左侧有 n 项

  • 一个经典的 big-O 函数是 log(n)，它总是对应于“包含 n 个项目的平衡树的高度”。你只要知道排序是 O(n log(n)) 就可以逃脱惩罚。

  • 最后，您只报告大 O 函数中增长最快的项，因为随着输入大小的增长，这将支配所有其他项。任何常数因子也会被丢弃，因为我们只对结果的缩放属性感兴趣。

例如，O(2(n^2) + n) = O(n^2)。

这里有两个例子。

冒泡排序 n 项

每次遍历项目都会将（至少）一个项目排序到位。因此，我们需要 n 次遍历来对所有项目进行排序。

O(bubble-sort(n)) = n * O(traversal(n))
                  = O(n * traversal(n))

项目的每次遍历都涉及 n - 1 个相邻的比较和交换操作。

O(traversal(n)) = (n - 1) * O(compare-and-swap)
                = O((n - 1) * O(compare-and-swap))

比较和交换是一个恒定时间操作。

O(compare-and-swap) = O(1)

收集我们的条款，我们得到：

O(bubble-sort(n)) = O(n * (n - 1) * 1)
                  = O(n^2 - n)
                  = O(n^2)

合并排序 n 个项目

合并排序自下而上工作，将项目合并成对，将成对成四，四成成八，依此类推，直到列表被排序。将每组这样的操作称为“合并遍历”。由于 n = 2 ^ log_2(n) 最多可以有 log_2(n) 个合并遍历，并且在每个级别上，我们都将要合并的子列表的大小加倍。所以，

O(merge-sort(n)) = log_2(n) * O(merge-traversal(n))
                 = O(log_2(n) * merge-traversal(n))

每个合并遍历遍历所有输入数据一次。每个输入项是至少一个比较和选择操作的主题，并且每个比较和选择操作选择一对项目中的一个来“发出”。因此

O(merge-traversal(n)) = n * O(compare-and-select)
                      = O(n * compare-and-select)

每个比较和选择操作都需要固定时间：

O(compare-and-select) = O(1)

收集术语，我们得到

O(merge-sort(n)) = O(log_2(n) * n * 1)
                 = O(n * log_2(n))
                 = O(n * log(n)), since change of log base is 
                                  multiplication by a constant.

呸呸呸！

于 2012-08-20T01:02:05.703 回答