![]() |
1
0
逐部分检查代码:
然后:
这也是O(N),因为:
最后:
令人惊讶的是,瓶颈就在这里(至少就O表示法而言)。中的元素数
排序后创建res的代码部分:
尽管在一个循环中,排序的成本加起来并不超过O(N logn),因为O(N logn)的成本假设有一个大用户。最多只能有几个大用户。 例如,假设系统中有K个相等的用户。这使得每个用户的排序成本为O(N/K log(N/K))。整个系统总计为O(N log(N/K))。如果K是常数,则变为O(N logn)。如果K是N的函数,那么O(nlog(N/K))小于O(nlogn)。 ,但这足以得到为什么它是O(N logn)而不是更糟的基本概念。
:算法以O(N logn)复杂度运行,其中N是输入文本的大小。 注意:复杂性计算有一个主要的假设,即在Python中,通过长度为L的字符串键访问map或set是一个O(L)操作。这通常是正确的,有一个完美的散列函数,而Python没有。 |
![]() |
Thomas Ahle · 递归联合查找是否可以优化? 9 年前 |