j******2
发帖数: 362 | 1 2分法是O(m*log(n))，
如果数组长度变化很大，可以先用O(n)把最小的选出来，总的复杂度就可以是O(n+min(
m)*log(n))。
如果n很大而m不大，就不要选min(m)。
大家觉得呢？ |
h****n
发帖数: 1093 | 2 二分的复杂度也是O（n×m）吧
两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
复杂度还是O（N×M）啊
你怎么个二分的 |
j******2
发帖数: 362 | 3 是我想错了。土了。那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
了。对吗？还有更简便的方法吗？
【在 h****n 的大作中提到】
: 二分的复杂度也是O（n×m）吧
: 两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
: 复杂度还是O（N×M）啊
: 你怎么个二分的
|
h****n
发帖数: 1093 | 4 这个其实只能叫divide and conquer
二分一般都是指binary search。。。
好像没法优化了，要非得说优化就按照你说的先找到最短的然后开始一个一个比
【在 j******2 的大作中提到】
: 是我想错了。土了。那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
: 了。对吗？还有更简便的方法吗？
|
j******2
发帖数: 362 | 5 那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
了。对吗
【在 h****n 的大作中提到】
: 这个其实只能叫divide and conquer
: 二分一般都是指binary search。。。
: 好像没法优化了，要非得说优化就按照你说的先找到最短的然后开始一个一个比
|
h****n
发帖数: 1093 | 6 恩。不过我觉得复杂度应该是O（N×avg（M））
【在 j******2 的大作中提到】
: 那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
: 了。对吗
|
j******2
发帖数: 362 | 7 每检测一个元素时不是同时也看了它是不是到队尾了吗？所以不会扫超过min(m)轮。
另外我在想：divide and conquer是不是只能把quadratic变成log linear，对本身
linear的问题没有帮助啊？
【在 h****n 的大作中提到】
: 恩。不过我觉得复杂度应该是O（N×avg（M））
|
d******i
发帖数: 76 | 8 对啊，这个怎么能用到二分查找呢？
逐个头比较吧，O(N * M) |
h****n
发帖数: 1093 | 9 你的M是指什么呀，我的M是指字符串的长度 avg M是指字符串的平均长度
具体M是多少和你字符串的排列是有关系的
考虑两种极端的情况，假设所有字符串的字符都是同一个字符，
第一种所有字符按照长度从长排到短，那么比较下来的长度就是AVG M
第二种就是所有字符按照长度从短到长排，那么比较下来的长度就是MIN M
divide conquer的复杂度可以用主定理来分析的，主要看最终的复杂度看分支数量，子
问题规模和合并操作的开销
T（n）=a(T/b) + O(n^d)
T（n）= n^d if d > logb a
= n^(logb a) if d < logb a
= n^d * lgn if d == logb a
【在 j******2 的大作中提到】
: 每检测一个元素时不是同时也看了它是不是到队尾了吗？所以不会扫超过min(m)轮。
: 另外我在想：divide and conquer是不是只能把quadratic变成log linear，对本身
: linear的问题没有帮助啊？
|
d******i
发帖数: 76 | 10 写的一个c++代码。 worst case O(N * M)
string longestCommonPrefix(vector &strs) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(strs.size() == 0) return "";
int longest = 0;
while(longest < strs[0].size())
{
for(int i = 1; i
{
if(longest == strs[i].size() || strs[i][longest] != strs[0][
longest])
return strs[0].substr(0, longest);
}
++longest;
}
return strs[0];
} |
|
|
j******2
发帖数: 362 | 11 咱们的M是一个意思。不管你咋么排，一旦扫到最短串的末梢，就终结了啊？
【在 h****n 的大作中提到】
: 你的M是指什么呀，我的M是指字符串的长度 avg M是指字符串的平均长度
: 具体M是多少和你字符串的排列是有关系的
: 考虑两种极端的情况，假设所有字符串的字符都是同一个字符，
: 第一种所有字符按照长度从长排到短，那么比较下来的长度就是AVG M
: 第二种就是所有字符按照长度从短到长排，那么比较下来的长度就是MIN M
: divide conquer的复杂度可以用主定理来分析的，主要看最终的复杂度看分支数量，子
: 问题规模和合并操作的开销
: T（n）=a(T/b) + O(n^d)
: T（n）= n^d if d > logb a
: = n^(logb a) if d < logb a
|
h****n
发帖数: 1093 | 12 假如从最长M排到最短1，那么最坏情况下 第一次需要比较M-1次，第二次需要比较M-2
次 以此类推
【在 j******2 的大作中提到】
: 咱们的M是一个意思。不管你咋么排，一旦扫到最短串的末梢，就终结了啊？
|
d******i
发帖数: 76 | 13 worst case = N * M, N 是元素个数，M是最后结果长度。 |
j******2
发帖数: 362 | 14 是N次不是M次吧？
2
【在 h****n 的大作中提到】
: 假如从最长M排到最短1，那么最坏情况下 第一次需要比较M-1次，第二次需要比较M-2
: 次 以此类推
|
h****n
发帖数: 1093 | 15 不对吧。。
考虑这样的例子
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
...
a
最后一行只有一个a，前面都是这么一大串
最后的结果长度是1 显然worst case不是N*1
【在 d******i 的大作中提到】
: worst case = N * M, N 是元素个数，M是最后结果长度。
|
h****n
发帖数: 1093 | 16 我表达不清吧
我指的是下面这样子的一个例子
aaaaa
aaaa
aaa
aa
a
第一次需要比较4次，第二次需要比较3次，以此类推
【在 j******2 的大作中提到】
: 是N次不是M次吧？
:
: 2
|
j******2
发帖数: 362 | 17 这种情况第二次扫完就结束拉。
【在 h****n 的大作中提到】
: 我表达不清吧
: 我指的是下面这样子的一个例子
: aaaaa
: aaaa
: aaa
: aa
: a
: 第一次需要比较4次，第二次需要比较3次，以此类推
|
d******i
发帖数: 76 | 18 错了，worst case = N *(M + 1) |
h****n
发帖数: 1093 | 19 恩我们的扫法不一样 我是一个字符串一个字符串扫 你是一个字符一个字符扫 你那种
更好点
【在 j******2 的大作中提到】
: 这种情况第二次扫完就结束拉。
|
