请问面试中考到的算法复杂度大家一般是靠直觉还是推导 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请问面试中考到的算法复杂度大家一般是靠直觉还是推导

请问面试中考到的算法复杂度大家一般是靠直觉还是推导# JobHunting - 待字闺中

s*A2013-04-20 07:04

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*a2013-04-20 07:04

2 楼

一般不会有很复杂的直觉一般不会有错误的
顶多分治得仔细想想吧

s*A2013-04-20 07:04

3 楼

谢谢
那Master theorem还需要记不？

【在 s****a 的大作中提到】

: 一般不会有很复杂的直觉一般不会有错误的
: 顶多分治得仔细想想吧

h*62013-04-20 07:04

4 楼

其实那不叫直觉。。。那也是以分析为基础的。

x*w2013-04-20 07:04

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得到最后结果
: 请问面试中大家一般都会按哪种做法？