关于时间复杂度的问题

爱上绝对路径 发布于 2012/03/04 19:23
阅读 573
收藏 1
有一个n*n的数组,只由1和0构成,并且在每一行1总出现在0的前面。如何设计算法使得最快查找出1最多的那一行?
加载中
0
dake
dake

先选一行(比如第一行)找到最后的1的位置比如下标为j,然后再查找剩下的N-1行对应的下标为j+1的位置,看是否为1,如果是就把此行记为1最长的行,j=j+1,如此直到N-1行全部比较完

也就是说找第一行中最后的1的下标(比如为j)要跟N个元素比较,然后再跟剩下N-1行的j+1下标比较。。。所以最快为O(N)

不知道对不对。。。

dake
dake
呵呵。。。。谢谢提醒。。我果然还是不会算时间复杂度。。。囧。。
liuex
liuex
这个是O(n*n)
0
liuex
liuex
"每一行1总出现在0的前面"是啥意思?是不是只能有1*0*这种情况,绝不可能出现11001100这种情况?如果是这样的话,我能想到的最快的是O(n*logn)
爱上绝对路径
爱上绝对路径
int i=0,j=0,row=0 while(i<n&&j<n) if(a[j][i]==0) j++ else i++; row=j
0
dake
dake

引用来自“liuex”的答案

"每一行1总出现在0的前面"是啥意思?是不是只能有1*0*这种情况,绝不可能出现11001100这种情况?如果是这样的话,我能想到的最快的是O(n*logn)
咦不对。。。。。我那个方法是两个非嵌套的循环 ,一个是O(N),一个是O(N-1),  那么O(N+N-1)=O(2N-1)不是O(N*N)
0
liuex
liuex

引用来自“dake”的答案

引用来自“liuex”的答案

"每一行1总出现在0的前面"是啥意思?是不是只能有1*0*这种情况,绝不可能出现11001100这种情况?如果是这样的话,我能想到的最快的是O(n*logn)
咦不对。。。。。我那个方法是两个非嵌套的循环 ,一个是O(N),一个是O(N-1),  那么O(N+N-1)=O(2N-1)不是O(N*N)

第一阶段:找到j,需要O(n)

第二阶段:你需要循环剩下n-1行中的(j,n]列,你要是只比较了j+1列的话,那算法本身就不是正确的了,考虑以下的输入:

1 0 0 0 0
1 1 1 1 1
1 1 0 0 0
1 1 1 0 0
1 0 0 0 0

我们约定从0开始计数。假设你从第0行开始计算,第一阶段执行完成后j=0,然后开始第二阶段,看1~4行的第1列是否为1,如果你不对j做循环for(i=j+1;i<n;i++)的话,那算法找出的结果是不正确的。

如果你做了循环的话,那么第二阶段就是O((n-j)*(n-1)),大概就是O(n*n)

爱上绝对路径
爱上绝对路径
有O(n)的。
少帮主
少帮主
1只能出现在0之前,也就说连续的1是不会出现的,你的例子不对吧
0
liuex
liuex

O(n*logn)的算法,就是对列使用二分法扫描,然后O(n)的遍历第j列中是否有1;

在上面的例子中:

第一次:扫描第(0+4)/2=2列,有1

第二次:扫描第(3+4)/2=3列,有1

第三次:扫描第(4+4)/2=4列,有1

第四次:二分法达到边界条件,结束

0
少帮主
少帮主

没想到技巧,这个不存在连续的1没法用上

算法:每行求和,取最大值的那行

需要全部扫描完数据算法复杂度为O(N^2) 

上面几位仁兄的做法我认为没有真的加速

爱上绝对路径
爱上绝对路径
1可以连续
少帮主
少帮主
等着其他答案
0
爱上绝对路径
爱上绝对路径
他的例子是对的,1出现在任何0之前
爱上绝对路径
爱上绝对路径
有o(N)的吧
少帮主
少帮主
1总出现在0的前面的理解有问题,我理解成可以1010,那这个问题就简单了了,每行二分法,n log(n) 的复杂度,经典的简单问题
0
少帮主
少帮主
二分搜索,n*log(n)
0
空杯子
空杯子

log(n) + log(log(n)) + log(log(log(n))) +...+log(log(log(...(log(n)))))

第1行,在n上二分

第2行,在log(n)上二分

...

第n行,在log(log(log(...(log(n)))))上二分,n-1层log

 

少帮主
少帮主
这什么跟什么啊, 在log(n) 上二分? 即使如此,也就是log(n)的复杂度,不需要后续那些无穷小的玩意了
0
空杯子
空杯子
呵呵,5、6年没做题了,等答案啊!
返回顶部
顶部