j*****y
发帖数: 1071 | | w****x
发帖数: 2483 | 2
二分
【在 j*****y 的大作中提到】
: 能有 sub-linear吗？
| j*****y
发帖数: 1071 | 3 复杂度能到多少 ?
【在 w****x 的大作中提到】
:
: 二分
| m******s
发帖数: 165 | 4 假设是m*n的表（m<=n）
朴素走对角线：最差O(n+m)
二分：最差O(m*log(2n/m))
即m==n时最差的情况下二分也是linear
【在 j*****y 的大作中提到】
: 能有 sub-linear吗？
| m*********g
发帖数: 4 | | j*****y
发帖数: 1071 | 6 二分的复杂度是
T(m, n) = T(m/2, n) + log(n)
这个怎么算阿?
【在 m******s 的大作中提到】
: 假设是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 的大作中提到】
: 二分的复杂度是
: T(m, n) = T(m/2, n) + log(n)
: 这个怎么算阿?
| j*****y
发帖数: 1071 | 8 多谢 :)
【在 m******s 的大作中提到】
: 二分的最差复杂度是（省略全部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)
: 需要注意到二分运气不好是要搜两边的。。。
|
|
