理解算法时间和空间复杂度需要哪种数学知识？

Question

理解算法时间和空间复杂度需要哪种数学知识？

algorithmmathtime-complexityspace-complexity

6

我一直在申请工作，每次被问到算法时间/空间复杂度的问题时，我都感到害怕和困惑。无论我读了多少，我的大脑似乎都被编程成不理解它们，我认为这是由于我数学基础非常差，因为曾经逃学。这可能不是通常的S.O问题，甚至可能因为涉及数学而被删除，但至少我希望能够通过这个问题找到下一步的方向。

- CaseyJones

至少对我来说，是第一年的微积分。 - nullpotent

常识和基本逻辑。 - user529758

离散数学值得一看。 - dangowans

3个回答

8

分析算法的时间/空间复杂度 - 高中数学知识就足够了。我在大学的第一学期学过这个，感觉还不错。

基础领域包括：

- 基本微积分（理解“极限”和“渐近线”是什么） - 级数计算（特别是算术级数的求和经常用到） - 组合数学基础（“有多少种选项可以...？”） - 多项式算术基础（p(x)+q(x)=?）

以上是分析算法复杂度的基础。计算“问题”的复杂度是更深入的领域，仍在研究中 - “复杂性理论”。这需要广泛的集合论、计算理论、高等微积分、线性代数等知识。

- amit

1

非常感谢Amit提供了如此详细和高度超链接的文章！我真的很感激 :) - CaseyJones

6

在IT技术方面，虽然了解微积分、求和序列和离散数学等方面是很好的事情，但根据您的问题和我的有限行业经验，我怀疑您的面试官并不期望您达到那个理解水平。

实际上，在没有进行太多数学思考的情况下，您可以就时间和空间复杂度做出有用的大O表述。以下是基础知识，我将使用时间复杂度来阐述，以使语言更加具体：

大O时间复杂度告诉您算法的最坏运行时间如何随其输入大小而变化。大O函数得出的实际数字是算法在给定输入大小上执行的恒定时间操作的指示。

因此，大O函数简单地计算算法将执行的恒定时间操作的数量。

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

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

如果算法按系列执行多个操作，则需要将它们的成本相加。

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

如果算法多次执行某个操作，则需要将操作的成本乘以执行次数。

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

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

经典的大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.

Ta daaaa！

- Rafe

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Christian Stieber · Accepted Answer

我不知道为什么职业人士会涉及到这个，所以这里只列举几个例子。"复杂性"只是提供算法使用多少时间（或内存）的指示。

现在，如果你有一个带有值的数组，访问给定索引处的值是O(1)--常数级的。无论数组中有多少元素，如果你有一个索引，就可以直接获取该元素。

然而，如果你正在寻找特定值，你将不得不查看每个元素（至少直到找到一个，但这对于复杂性并不重要）。因此，在随机数组中进行搜索是O(n)：运行时间与元素数量相对应。

另一方面，如果你有一个排序的数组，那么可以进行"二分查找"，它的复杂度将是O(log n)。"log n"是以2为底的对数，基本上是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个元素的数组，它需要4次“操作”，如果数组有3个元素，则需要9次操作，如果数组有4个元素，则需要16次操作，以此类推。考虑到仅具有1000个元素的数组已经需要1000*1000 = 1百万比较才能完成排序，这是相当糟糕的。这被称为指数增长，当然可以变得更糟：O(n^3)，O(n^4)等等，变得越来越糟。

一个“好”的排序算法是O(n*log n)。假设一个包含1024个元素的数组，这将需要1024*10=10240次比较--远比我们之前的1百万好多了。

只需将这些O(...)视为运行时行为（或如果应用于内存则为内存占用）的指示符。我确实输入了实际数字，以便您可以看到数字如何变化，但那些并不重要，并且通常这些复杂性是最坏的情况。尽管如此，通过仅查看数字，“常量时间”显然是最佳的，指数增长总是不好的，因为运行时（或内存使用）会非常快速地增加。

编辑：另外，您并不真正关心常数因素；通常不会看到“O(2n)”这种情况。这仍然是“O(n)”--运行时间与元素数量直接相关。