我一直在申请工作,每次被问到算法时间/空间复杂度的问题时,我都感到害怕和困惑。无论我读了多少,我的大脑似乎都被编程成不理解它们,我认为这是由于我数学基础非常差,因为曾经逃学。这可能不是通常的S.O问题,甚至可能因为涉及数学而被删除,但至少我希望能够通过这个问题找到下一步的方向。
我一直在申请工作,每次被问到算法时间/空间复杂度的问题时,我都感到害怕和困惑。无论我读了多少,我的大脑似乎都被编程成不理解它们,我认为这是由于我数学基础非常差,因为曾经逃学。这可能不是通常的S.O问题,甚至可能因为涉及数学而被删除,但至少我希望能够通过这个问题找到下一步的方向。
我不知道为什么职业人士会涉及到这个,所以这里只列举几个例子。"复杂性"只是提供算法使用多少时间(或内存)的指示。
现在,如果你有一个带有值的数组,访问给定索引处的值是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(bubble-sort(n)) = n * O(traversal(n))
= O(n * traversal(n))
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.