c********t
发帖数: 5706 | 1 LC 4Sum O(n^3)是time complexity下届吗？我怎么觉得不是呢？ |
f*******s
发帖数: 182 | |
e*******s
发帖数: 1979 | 3 n^2
【在 c********t 的大作中提到】
: LC 4Sum O(n^3)是time complexity下届吗？我怎么觉得不是呢？
|
c********t
发帖数: 5706 | 4 应该是 O(n^2 * m)吧 m is average duplicate 2sum number
1，2，3，4，5，6
target 14
要找出所有解，肯定要处理2sum的duplicate
【在 e*******s 的大作中提到】
: n^2
|
c********t
发帖数: 5706 | 5 看看这个帖子，他的证明好像没问题啊。O(n^3)是下届
https://discuss.leetcode.com/topic/27445/lower-bound-n-3/14
我现在突然之间全糊涂了。Big O是upper bound of all cases啊，我一直以为是
average case呢。
那么我们为什么说quick sort是 O(nlogn)? 如果是worst case不是O(n^2)吗？是因为
优化partition可以避免吗？
【在 f*******s 的大作中提到】
: 当然不是 http://www.sigmainfy.com/blog/4sum-problem-analysis-different-time-complexity.html
|
i*****r
发帖数: 265 | 6 quick sort 一直是n^2。只是一般情况下run的比nlgn的都快而已
【在 c********t 的大作中提到】
: 看看这个帖子，他的证明好像没问题啊。O(n^3)是下届
: https://discuss.leetcode.com/topic/27445/lower-bound-n-3/14
: 我现在突然之间全糊涂了。Big O是upper bound of all cases啊，我一直以为是
: average case呢。
: 那么我们为什么说quick sort是 O(nlogn)? 如果是worst case不是O(n^2)吗？是因为
: 优化partition可以避免吗？
|
c********t
发帖数: 5706 | 7 人生观颠覆了，面试的时候，一旦有sort，我都是告诉是O(nlogn) 复杂度，面试官从
没异议。 难道以后面试当问到复杂度的时候，每次都要说清楚average, worst case
和 best case啊，很耽误时间的。
【在 i*****r 的大作中提到】
: quick sort 一直是n^2。只是一般情况下run的比nlgn的都快而已
|
s*a
发帖数: 267 | 8 尽量用theta，theta是average复杂度。
【在 c********t 的大作中提到】
: 人生观颠覆了，面试的时候，一旦有sort，我都是告诉是O(nlogn) 复杂度，面试官从
: 没异议。 难道以后面试当问到复杂度的时候，每次都要说清楚average, worst case
: 和 best case啊，很耽误时间的。
|
s**********g
发帖数: 14942 | 9 一般说average的O问题应该不大
但是如果能同时说出worst的O，应该可以加分
如果面试官想问worst O，可能会follow up问。。
【在 c********t 的大作中提到】
: 人生观颠覆了，面试的时候，一旦有sort，我都是告诉是O(nlogn) 复杂度，面试官从
: 没异议。 难道以后面试当问到复杂度的时候，每次都要说清楚average, worst case
: 和 best case啊，很耽误时间的。
|
