s****A
发帖数: 80 | 1 直觉的意思就是
比如一般看到嵌套循环,就知道大概是n^2
看到从树的root到leaf的操作，大概就是lgn
推导的话就是比较严谨点的，比如heap的heapify操作，先要想到size为n的binary
tree左右两个子树每个size最多不超过2n/3,然后得到T(n)<=T(2n/3)+O(1),用master
theorem得到最后结果
请问面试中大家一般都会按哪种做法？ |
s****a
发帖数: 794 | 2 一般不会有很复杂的 直觉一般不会有错误的
顶多分治得仔细想想吧 |
s****A
发帖数: 80 | 3 谢谢
那Master theorem还需要记不？
【在 s****a 的大作中提到】
: 一般不会有很复杂的 直觉一般不会有错误的
: 顶多分治得仔细想想吧
|
h******6
发帖数: 2697 | |
x*********w
发帖数: 533 | 5
很多就是画recursion tree硬看？比如merge sort?
heapify等可以写个数列，发现一只是收敛的那就是n了？
有些比如用队列实现max number in moving window的算O(n)就是每个元素只如队列出
队列一次？
有些用到组合的，比如permutation, combination啥的？
计算平均时间复杂度用到些概率，期望啥的... 不过这个有点难。。。
【在 s****A 的大作中提到】
: 直觉的意思就是
: 比如一般看到嵌套循环,就知道大概是n^2
: 看到从树的root到leaf的操作，大概就是lgn
: 推导的话就是比较严谨点的，比如heap的heapify操作，先要想到size为n的binary
: tree左右两个子树每个size最多不超过2n/3,然后得到T(n)<=T(2n/3)+O(1),用master
: theorem得到最后结果
: 请问面试中大家一般都会按哪种做法？
|
f********4
发帖数: 988 | 6 靠直觉猜一个先
要是看面试官表示不对。。
就再仔细想想。。 |
s****a
发帖数: 794 | 7 不需要 这种东西google一下1分钟就出来 知道有这个东西 会用就得了
我遇到过的最复杂的也就是merge sort和一个稍微有些复杂的循环
【在 s****A 的大作中提到】
: 谢谢
: 那Master theorem还需要记不？
|
