什么类型的数学需要理解算法时间和空间复杂性？

Question

我一直在申请工作,每当我听到有关算法时间/空间复杂性的问题时,我都会畏缩和磕磕绊绊.无论我读了多少,我的大脑似乎都被编程为不能得到任何一个,我认为原因在于我因为逃学而导致数学背景很低.这可能不是通常的SO问题,甚至可能因为从根本上讲数学而被删除,但至少我希望我能找出这个问题的下一步.

Answer 1

要分析算法的时间/空间复杂性-高中知识应该很好。我在大学学习了这个。在我的第一学期，我还好。

基础知识的兴趣领域是：

• 基本演算（了解“极限”和渐近线是什么）
• 级数计算（尤其是经常使用算术级数的总和）
• 组合语言的基础知识（“ ...有多少选择？”）
• 多项式算术基础（p（x）+ q（x）=？）

以上对于分析算法的复杂性是正确的。计算问题的复杂性是更深层次的领域，这仍在研究复杂性理论中。这需要对集合论，计算论，高级微积分，线性代数等有广泛的了解。

Answer 2

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

现在，如果您有一个带有值的数组，则在给定索引处访问值的值为O（1）-常量。数组中有多少个元素都没有关系，如果您有索引，则可以直接获取该元素。

另一方面，如果您要查找特定值，则别无选择，只能查看每个元素（至少直到找到一个元素为止，但这与复杂性无关紧要）。因此，在随机数组中搜索为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 = 1百万个比较才能进行排序，这实际上非常糟糕。这称为指数增长，它当然会变得更糟：O（n ^ 3），O（n ^ 4）等。情况越来越糟。

“好的”排序算法是O（n * log n）。假设一个数组包含1024个元素，那么与之相比，这将是1024 * 10 = 10240，比我们以前拥有的100万要好得多。

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

编辑：而且，您对常数因子不是很感兴趣；您通常不会看到“ O（2n）”。仍然是“ O（n）”-运行时直接与元素数量有关。

Answer 3

虽然了解微积分,求和系列和离散数学都是好事,但从你的问题和我在工业界的有限经验来看,我怀疑你的面试官是否期望这种理解水平.

在实践中,您可以制作有关时间和空间复杂性的有用的大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))就可以逃脱.

• 最后,您只报告big-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!