请问现在H4签证的有效期是 1 年多次往返吗？# Immigration - 落地生根
j*2
1 楼
2分法是O(m*log(n))，
如果数组长度变化很大，可以先用O(n)把最小的选出来，总的复杂度就可以是O(n+min(
m)*log(n))。
如果n很大而m不大，就不要选min(m)。
大家觉得呢？
如果数组长度变化很大，可以先用O(n)把最小的选出来，总的复杂度就可以是O(n+min(
m)*log(n))。
如果n很大而m不大，就不要选min(m)。
大家觉得呢？
f*h
2 楼
现在H1 有效期是 1 年多次往返了，有人知道H4 也是吗？ 多谢！
h*n
3 楼
二分的复杂度也是O（n×m）吧
两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
复杂度还是O（N×M）啊
你怎么个二分的
两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
复杂度还是O（N×M）啊
你怎么个二分的
e*r
4 楼
去visa版问问？
【在 f********h 的大作中提到】
: 现在H1 有效期是 1 年多次往返了，有人知道H4 也是吗？ 多谢！
【在 f********h 的大作中提到】
: 现在H1 有效期是 1 年多次往返了，有人知道H4 也是吗？ 多谢！
j*2
5 楼
是我想错了。土了。那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
了。对吗？还有更简便的方法吗？
【在 h****n 的大作中提到】
: 二分的复杂度也是O（n×m）吧
: 两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
: 复杂度还是O（N×M）啊
: 你怎么个二分的
了。对吗？还有更简便的方法吗？
【在 h****n 的大作中提到】
: 二分的复杂度也是O（n×m）吧
: 两两比较 N/2 + N/4 + N/8 + ...+ 1 = N
: 复杂度还是O（N×M）啊
: 你怎么个二分的
h*n
6 楼
这个其实只能叫divide and conquer
二分一般都是指binary search。。。
好像没法优化了，要非得说优化就按照你说的先找到最短的然后开始一个一个比
【在 j******2 的大作中提到】
: 是我想错了。土了。那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
: 了。对吗？还有更简便的方法吗？
二分一般都是指binary search。。。
好像没法优化了，要非得说优化就按照你说的先找到最短的然后开始一个一个比
【在 j******2 的大作中提到】
: 是我想错了。土了。那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
: 了。对吗？还有更简便的方法吗？
j*2
7 楼
那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
了。对吗
【在 h****n 的大作中提到】
: 这个其实只能叫divide and conquer
: 二分一般都是指binary search。。。
: 好像没法优化了，要非得说优化就按照你说的先找到最短的然后开始一个一个比
了。对吗
【在 h****n 的大作中提到】
: 这个其实只能叫divide and conquer
: 二分一般都是指binary search。。。
: 好像没法优化了，要非得说优化就按照你说的先找到最短的然后开始一个一个比
h*n
8 楼
恩。不过我觉得复杂度应该是O（N×avg（M））
【在 j******2 的大作中提到】
: 那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
: 了。对吗
【在 j******2 的大作中提到】
: 那就在扫的时候自动检测了最短的了，所以直接就是O(n*min(m))
: 了。对吗
j*2
9 楼
每检测一个元素时不是同时也看了它是不是到队尾了吗？所以不会扫超过min(m)轮。
另外我在想：divide and conquer是不是只能把quadratic变成log linear，对本身
linear的问题没有帮助啊？
【在 h****n 的大作中提到】
: 恩。不过我觉得复杂度应该是O（N×avg（M））
另外我在想：divide and conquer是不是只能把quadratic变成log linear，对本身
linear的问题没有帮助啊？
【在 h****n 的大作中提到】
: 恩。不过我觉得复杂度应该是O（N×avg（M））
d*i
10 楼
对啊，这个怎么能用到二分查找呢？
逐个头比较吧，O(N * M)
逐个头比较吧，O(N * M)
h*n
11 楼
你的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的问题没有帮助啊？
具体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
12 楼
写的一个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];
}
string longestCommonPrefix(vector
// 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
13 楼
咱们的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 的大作中提到】
: 你的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
14 楼
假如从最长M排到最短1，那么最坏情况下 第一次需要比较M-1次，第二次需要比较M-2
次 以此类推
【在 j******2 的大作中提到】
: 咱们的M是一个意思。不管你咋么排，一旦扫到最短串的末梢，就终结了啊？
次 以此类推
【在 j******2 的大作中提到】
: 咱们的M是一个意思。不管你咋么排，一旦扫到最短串的末梢，就终结了啊？
d*i
15 楼
worst case = N * M, N 是元素个数，M是最后结果长度。
j*2
16 楼
是N次不是M次吧？
2
【在 h****n 的大作中提到】
: 假如从最长M排到最短1，那么最坏情况下 第一次需要比较M-1次，第二次需要比较M-2
: 次 以此类推
2
【在 h****n 的大作中提到】
: 假如从最长M排到最短1，那么最坏情况下 第一次需要比较M-1次，第二次需要比较M-2
: 次 以此类推
h*n
17 楼
不对吧。。
考虑这样的例子
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
...
a
最后一行只有一个a，前面都是这么一大串
最后的结果长度是1 显然worst case不是N*1
【在 d******i 的大作中提到】
: worst case = N * M, N 是元素个数，M是最后结果长度。
考虑这样的例子
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
...
a
最后一行只有一个a，前面都是这么一大串
最后的结果长度是1 显然worst case不是N*1
【在 d******i 的大作中提到】
: worst case = N * M, N 是元素个数，M是最后结果长度。
h*n
18 楼
我表达不清吧
我指的是下面这样子的一个例子
aaaaa
aaaa
aaa
aa
a
第一次需要比较4次，第二次需要比较3次，以此类推
【在 j******2 的大作中提到】
: 是N次不是M次吧？
:
: 2
我指的是下面这样子的一个例子
aaaaa
aaaa
aaa
aa
a
第一次需要比较4次，第二次需要比较3次，以此类推
【在 j******2 的大作中提到】
: 是N次不是M次吧？
:
: 2
j*2
19 楼
这种情况第二次扫完就结束拉。
【在 h****n 的大作中提到】
: 我表达不清吧
: 我指的是下面这样子的一个例子
: aaaaa
: aaaa
: aaa
: aa
: a
: 第一次需要比较4次，第二次需要比较3次，以此类推
【在 h****n 的大作中提到】
: 我表达不清吧
: 我指的是下面这样子的一个例子
: aaaaa
: aaaa
: aaa
: aa
: a
: 第一次需要比较4次，第二次需要比较3次，以此类推
d*i
20 楼
错了，worst case = N *(M + 1)
h*n
21 楼
恩我们的扫法不一样 我是一个字符串一个字符串扫 你是一个字符一个字符扫 你那种
更好点
【在 j******2 的大作中提到】
: 这种情况第二次扫完就结束拉。
更好点
【在 j******2 的大作中提到】
: 这种情况第二次扫完就结束拉。
相关阅读
485需要提交i864表？关于F1 毕业后的工作问题OPT or F2 or GreenCard事实证明各种inquiry的不靠谱，以及长期斗争经验485申请 可以替老婆签字吗托朋友，老板找的独立推荐人，draft怎么编？关于ISI Web of Knowledge journal排名【2016年1月第55绿】TSC转NSC转local officereview opportunity要推荐信的email的title一般怎么写能引起别人注意？AOS期间邀请父母来美签证时，自己的身份选什么？food science 审稿Re: 回馈：生物土博，单亲妈妈，大学到公司 (转载)140已批，拿到485之前工作怎么办？？？？485期间，F1被终止【2016年1月第64绿】485 TSC Oct 23 RD approved会议审稿次数问题副申请人没有SSN有ITIN，不用填吧？【2016年1月第53, 54绿】给TSC的童鞋们打气：未必要羡慕转去NSC的Eigenfactor® score 的rank， NSC EB1A 承认么？