面试了一个在ACM拿过奖的人。

cjaizss

shan_ghost 发表于 2013-12-13 15:04
算法复杂度描述的是，一个算法随着处理对象的数目n的增长，所需时间、空间与n之间的函数关系（的粗略估计） ...

纠正一下,不是粗略估计,而是严格的无穷大级别

lz小骆驼

人才啊         回复 19# shang2010


   

A.com

这帖子真欢乐lol

exprosic

一切面试题都是纸老虎

按定义来看，对于 f(n)∈O(g(n)) 里 g(n)的阶是不设上限的
所以对于1,2题，都答 O(n^100) 不能算错

starwing83

回复 94# exprosic


    对一个算法问时间复杂度，通常问的是某个操作相对某种输入规模的函数关系，通常只关心增长最快的项目。从这个角度上来说，一个特定算法的时间复杂度，在一个指定的输入规模的计量下，是确定了的——至于找不找得到，那是另外一回事儿。

寻找算法的时间复杂度，是先找到这个算法的时间复杂度的一个上界，然后慢慢逼近下界，最后找到增长最快的最小复杂度，就是我们知道的对时间复杂度的一个粗略估计。

很显然，如果这种粗略估计粗略到了完全没有任何实用价值的地步，那么这种估计本身就是不合格的，这种不合格你完全可以说是“不正确”。

那么，“实用价值”是什么呢？

对于一个待解决的问题，其时间复杂度是不一定的，取决于这个问题的特质，和你使用的算法。我们需要找到的，是针对这个问题的最优时间复杂度，即，所有可能解决这个问题的算法中，时间复杂度最低的那个，寻找到这个算法的最有时间复杂度，可以使用“下界理论”来寻找所有算法复杂度的下界。

这就是时间复杂度的实用价值——用来对不同的算法进行比较，从而进行取舍。都是O(n^100)显然是没有办法取舍的，从而这个复杂度估计就是没价值的。

对复杂度的估计，采取不同的方法，从而导致精度不一样，如果误差太大——超过了客观的时间复杂度本身的增长速度太多，同样会起不到比较的效果，所以依然是没有意义的。

说白了，人家根本没说是大O小O还是Θ，你急个啥

grdxyxy

回复 88# shan_ghost


    是#pragma pack吧

叶叶叶Yeah

回复 95# starwing83


    肯定是大神，虽然我不太明白你在说什么。

liuiang

这算正常吧，之前公司一个硬件的哥么，跑我这吐槽，说公司高薪聘的一个博士，居然连eeprom都不知道是什么。

我除了苦笑，只能推荐他看看《庄子》了。

weishuo1999

也谈一下笔试面试，对于工作3年以下的一般都会尝试笔试一下，但是其实只看对方有没有画满，不看有没有做对，做满了就行
3年以上的一般就不笔试了，不然会被面试者鄙视了吧

面试主要问对方做什么，再问一些细节，细节里面见真章，如果没细节不够好，就看看愿不愿意学，聪明不聪明，最后比较一下
待遇要求，或者要，或者推荐其他公司，或者放弃

wangjun0220

本人表示什么都不会啊～