j*****y 发帖数: 1071 | | w****x 发帖数: 2483 | 2
二分
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能有 sub-linear吗?
| j*****y 发帖数: 1071 | 3 复杂度能到多少 ?
【在 w****x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 二分
| m******s 发帖数: 165 | 4 假设是m*n的表(m<=n)
朴素走对角线:最差O(n+m)
二分:最差O(m*log(2n/m))
即m==n时最差的情况下二分也是linear
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 能有 sub-linear吗?
| m*********g 发帖数: 4 | | j*****y 发帖数: 1071 | 6 二分的复杂度是
T(m, n) = T(m/2, n) + log(n)
这个怎么算阿?
【在 m******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 假设是m*n的表(m<=n) : 朴素走对角线:最差O(n+m) : 二分:最差O(m*log(2n/m)) : 即m==n时最差的情况下二分也是linear
| m******s 发帖数: 165 | 7 二分的最差复杂度是(省略全部big-O):
T(1,n) = logn
T(m,1) = logm
T(m,n) = max_j{T(m/2,j) + T(m/2,n-j)} + logn
要费一点力气,最终可以搞出来
T(m,n) = mlog(2n/m)
需要注意到二分运气不好是要搜两边的。。。
【在 j*****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 二分的复杂度是 : T(m, n) = T(m/2, n) + log(n) : 这个怎么算阿?
| j*****y 发帖数: 1071 | 8 多谢 :)
【在 m******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 二分的最差复杂度是(省略全部big-O): : T(1,n) = logn : T(m,1) = logm : T(m,n) = max_j{T(m/2,j) + T(m/2,n-j)} + logn : 要费一点力气,最终可以搞出来 : T(m,n) = mlog(2n/m) : 需要注意到二分运气不好是要搜两边的。。。
|
|