由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - Young table的搜索最快能到多少阿?
相关主题
关于找最大半径K子集的DP题的总结(更新非DP算法)问个面试题目
复杂度4sum的那道题
一个题求暴力fibonacci的复杂度
问uber的一道题上楼梯问题的时间复杂度是o(n)还是 nlogn?
Fibonacci序列的时间和空间复杂度是多少呀?我对G有心理阴影。。
也问一个median的问题LI这题是不是没有比linear更好的解法了?
问道题问个复杂度
谁给个数组分段题二分法的总结啊?LCA复杂度是多少
相关话题的讨论汇总
话题: 二分话题: young话题: 复杂度话题: 最差话题: linear
进入JobHunting版参与讨论
1 (共1页)
j*****y
发帖数: 1071
1
能有 sub-linear吗?
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)
: 需要注意到二分运气不好是要搜两边的。。。

1 (共1页)
进入JobHunting版参与讨论
相关主题
LCA复杂度是多少Fibonacci序列的时间和空间复杂度是多少呀?
LCA复杂度也问一个median的问题
算法空间复杂度的小白问题问道题
问一个search in rotated array的问题谁给个数组分段题二分法的总结啊?
关于找最大半径K子集的DP题的总结(更新非DP算法)问个面试题目
复杂度4sum的那道题
一个题求暴力fibonacci的复杂度
问uber的一道题上楼梯问题的时间复杂度是o(n)还是 nlogn?
相关话题的讨论汇总
话题: 二分话题: young话题: 复杂度话题: 最差话题: linear