B**********2
发帖数: 923 | 1 首先感谢microleo，给我推荐
电话两轮，一个聊天，一个简单的电面。
Coding Test 一轮，题目为Spread Sheet，大家可以自行Google
得到Positive Feedback
5月8号 On site
分别两个工程师两个项目经理
鉴于每个人多聊了一会我以前的Project，所以每个人问1到3个问题不等。
----------------- 割割割割割割割割 -----------------------------
Q: Spread Sheet 如果太大，不能整个Load进内存来处理。但是可以有多个
机器按照一定的信息读本机文件。假设Spread Sheet每个连通片的计算量
一个机器能够处理
A: Virtually的建立无向连通图，用DFS获得连通片，每个连通片交给一个主机来计算
----------------- 割割割割割割割割 -----------------------------
Q: 给一个森林和已知两个节点，求最近公共祖先，如果没有，返回NULL
A: 我说啥语言没有什么区别，先上伪码，MIT Press Algorithm ... 阅读全帖 |
|
e*******8
发帖数: 94 | 2 哎，大牛我可不敢当啊-_-bbbb
我刚才想错了，那步preprocess也需要O(nlogn).
完整的算法大致是这样：
１.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
所以最后整个算法的时间复杂度是O(nlogn). |
|
e*******8
发帖数: 94 | 3 哎，大牛我可不敢当啊-_-bbbb
我刚才想错了，那步preprocess也需要O(nlogn).
完整的算法大致是这样：
１.按结束时间对n个intervals排序。时间复杂度是O(nlogn).
２.定义f(i)为第i个interval的最偏右的不重叠的interval的index：这一步可以用
binary search，所以时间复杂度是O(n log n). 用来保存f(i)的数组需要O(n)的space.
3. recursion的公式: OPT(j) = max{w_j + OPT(f(j)), OPT(j-1)}, 从j＝１填到j＝n
，时间复杂度是O(n).用来保存OPT(j)的数组需要O(n)的space.
所以最后整个算法的时间复杂度是O(nlogn). |
|
e*******s
发帖数: 1979 | 4 【 以下文字转载自 Automobile 讨论区 】
发信人: jamesgordon (高登大爷), 信区: Automobile
标 题: 丰田工程师真的该枪毙啊 (转载)
发信站: BBS 未名空间站 (Sun Nov 3 21:23:20 2013, 美东)
【 以下文字转载自 Auto_Fans 俱乐部 】
发信人: andrews (旱鸭子), 信区: Auto_Fans
标 题: 丰田工程师真的该枪毙啊
发信站: BBS 未名空间站 (Sun Nov 3 00:14:23 2013, 美东)
看下面的这文章，我是无语了……
以前不知道什么是＂在看不到的地方偷工减料＂， 这回见识了。 以后不敢买丰田车了
转贴自：http://club.tgfcer.com/thread-6817371-1-1.html 网友Kuzuryuusen的文章
----------------------------
【第一部分】背景简介
前几年闹得沸沸扬扬的丰田刹不住事件最近又有新进展。十月底俄克拉荷马的一次庭审
，2007年一辆2005年凯美瑞暴冲（Unintended Acceler... 阅读全帖 |
|
a*********2
发帖数: 194 | 5 关注本版有几个月了，一直没怎么发帖，发下今天下午G家onsite的面经。
由于面试的国人大哥说了不要放面经，我也答应了，就不说具体题目了，笼统地说下题
目类别和感受。
上午两个人，一个年轻老美，一个国人大哥。
年轻老美问了个机器人走网格的题，虽然没有做过，不过类似的题目看过一些，所以很
容易就用dp写了一个。之后就是聊些我做的科研，g家做的类似项目，职业规划等等。
国人大哥面我，上来出了个很简单的string题，直接水过，后来出了个比较难的string
题，只让说了想法，没让写程序，估计那复杂度写起来要悲剧。。。感谢国人大哥的放
水！大家要互相帮助阿。可惜不知道这位大哥的email和全名，不然要写个感谢信。
下午三个，两个美国老头，目测都60以上把（看来老美一点年龄歧视都没有阿），一个
40多老美。
第一个美国老头上来把手机拿出来说正在玩一个游戏，问我怎么编程解决，一个类似华
容道的游戏，就说了下bfs的思路，怎么建立图，也没让写程序。后来问了简单的个概
率题，我不知道怎么卡住了，后来经过提示搞出来了。后来又问了个矩阵里面搜索元素
的题，binary search搞定。问复杂度，由于和... 阅读全帖 |
|
s*****p
发帖数: 108 | 6 看了本版很多面经，获益良多，所以我也把我近期面试的过程写下来，并且给出一些我
对系统设计题的想法，希望对正在找工作的人会有一点帮助。我的背景非cs非ee，不过
和编程相关，而且平时自己也经常写写程序。cc150和leetcode各刷了两遍。这次只申
请了F和G，最后F悲剧，G offer。
由于我有一些iOS的经验，所以申请F时申请的是iOS developer的职位。
F电面只有一轮：
先问了一些近期做的项目，然后编程是实现UIControl里的几个method，比如addTarget
什么的。不难。电面过后一周就安排了onsite。
F onsite 有4轮，全是白人：
1. 问了一些behavior的问题，比如简历里写的项目什么的，然后还问了最喜欢
facebook app的哪个功能，有什么可以改进的地方，怎么改进。还有为什么想去
Facebook。这些问题我基本都已经准备过，所以应该都答得不错。最后给了一个简单的
coding题，就是逆序打印链表里的值。我说了三个方法，一个是递归，一个是用stack
（和递归也差不多），还有就是先反转链表，按顺序打印，然后再反转一次恢复原状。
... 阅读全帖 |
|
k*******a
发帖数: 433 | 7 第一题就是把两个单词的序号分别放到两个顺序容器里，然后分别从两个顺序容器取一
个值，计算差的绝对值最小的。
两道题他们都没啥评价，就是第一题让给我改了bug。
我觉得可能过不了面试，因为第二道题我的时间复杂度说错了。
按照我的代码的写法，时间复杂度应该是n^n，可我说了n!
其实我的递归算法写得不好，时间复杂度就是n^n,可是我却告诉他是n的阶乘
估计挂了
面试完之后我才知道时间复杂度说错了 |
|
M**********g
发帖数: 59 | 8 面试的是一个 国人phd。
1.pow(double a, int b)没什么说的，注意overflow就行
2.实现2sum
interface TwoSum{
//存储用户输入的数
void store(int input){
}
//判断是否有两个数的和是val
boolean test(int val){
}
}
要求输入有重复，首先实现test的复杂度O(n) store的复杂度常数（用hashmap）
然后实现store的复杂度是o(n)，test的复杂度是常数（用hashset）
最后考虑并发问题，两个方法同是被调用的时候（互斥锁）
很好的面试题，考察的挺全面，实际中也会碰到这样的问题，给大家分享一下。因为多
线程编程不是很了解，估计已挂。面试的时候又紧张。 |
|
M*******n
发帖数: 10087 | 9 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 不刷题进Google的经历
发信站: BBS 未名空间站 (Thu Jun 11 18:34:25 2015, 美东)
没有马甲，又不想被认出，所以跑到这里发帖，希望有人能转到Jobhunting板上。
在Jobhunting板上混了很久了，看到大家的共识就是：不管你工作多久，想去FLG必须
刷题。（例外也有人提到，但是似乎不是Google research的职位，就是功成名就的大
牛，都不是普通码工的情况）我自己和周围认识人的经历似乎也验证了这一点。不过最
近我终于在没有刷任何题的情况下拿到了G家的offer，看起来这种“共识”也并不是
100%正确的。由于Jobhunting板上这种经历似乎不多，所以详细写一下，供大家分享，
也给像我一样不愿刷题的人鼓励一下。这个帖子主要侧重分享面试经历，面经记不太清
了，不是太多，放在最后。
我自己四年前也曾经认真刷过0.9遍Leetcode题目，去过G家on site一次。当时自我感
觉答得还不错，但是最终还是被... 阅读全帖 |
|
A*******e
发帖数: 2419 | 10 * Multi task design
用户可以法请求要求某一个task在某一时间开始执行。这样的请求可能很多。设计一个
系统处理这样的请求。问如果处理系统是local的（和发请求的在一起）或者是remote
的有哪些设计上的不同。
这个没怎么实际做过，只能随便侃侃，简单写了几行伪代码。
汗，没看懂要设计啥。什么叫处理这样的请求？同一时间请求太多，资源不够咋办？
* Quad-tree intersection
一个quad－tree表示一个2D的黑白图，每个节点都是平行于坐标轴的矩形，节点的
value 0和1表示黑和白。如果一个节点全黑或全白就是叶子，否则就继续剖分成四份。
要求写一个函数求两个quad－tree的交。
这个比较简单，写了一个递归的程序，不确定是否有bug。
什么是两个树的交？
* Base64 encoding
先解释了一下何谓Base64 encoding（http://en.wikipedia.org/wiki/Base64），然后要求写一个函数将一个字符串按Base64编码。
用位操作实现，写了简单的代码，不确定是否是他想要的答案。
* Swizzle so... 阅读全帖 |
|
f********t
发帖数: 6999 | 11 【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: 不刷题进Google的经历
发信站: BBS 未名空间站 (Thu Jun 11 18:34:25 2015, 美东)
没有马甲，又不想被认出，所以跑到这里发帖，希望有人能转到Jobhunting板上。
在Jobhunting板上混了很久了，看到大家的共识就是：不管你工作多久，想去FLG必须
刷题。（例外也有人提到，但是似乎不是Google research的职位，就是功成名就的大
牛，都不是普通码工的情况）我自己和周围认识人的经历似乎也验证了这一点。不过最
近我终于在没有刷任何题的情况下拿到了G家的offer，看起来这种“共识”也并不是
100%正确的。由于Jobhunting板上这种经历似乎不多，所以详细写一下，供大家分享，
也给像我一样不愿刷题的人鼓励一下。这个帖子主要侧重分享面试经历，面经记不太清
了，不是太多，放在最后。
我自己四年前也曾经认真刷过0.9遍Leetcode题目，去过G家on site一次。当时自我感
觉答得还不错，但是最终还是被... 阅读全帖 |
|
r******y
发帖数: 21 | 12 这周二的时候onsite的。
phone是skype面，一位白人，预定是45分钟。先聊了30分钟简历，然后面试官给了一题
Anagram，很简单，用python解了。followup是不用sort，如何判断两个string是不是
anagram，用int[256]就可以。
Onsite面，先是recruiter带着参观了公司10分钟。
Onsite第一面，印度小哥，说是做transaction的，给了一道fib，分别写了递归和迭代
解，然后问了各自的时间复杂度，空间复杂度。下一道题是power set，求是否存在一
个power set满足某个sum，因为整个set都是正数，所以可以剪枝，然后问了一下时间
复杂度。因为做得比较快，小哥有给了一道sqrt，我给了两个解法，一个二分，一个牛
顿法。印度小哥很满意，问了一下问题就离开了。
Onsite第二面。给一个map，key是class，value是一个list，list里包括这个class对
应的所有lectures的时间段。然后再给一个class的list,求是否能在这个map里，对每
个class至少找到一个时间段，而且各时间段之间... 阅读全帖 |
|
n*******t
发帖数: 6 | 13 我说，“大姐，array.size()，的复杂度是O（n）啊！第二种方法，用了.size(),所以
复杂度至少是O(n), 不能更少了。"
对方说:" 那你给的第一个解法也要用到.size(),那除掉.size()那步，我可以专门选一
个极端的情况，让第二个走n/2， 第一个走 n。 所以第二个快。"
为了说某种算法快，可以去掉这个算法里面O(n)的部分，然后选一个极端的情况，不到
n步，然后这个算法就比另一个O(n)快了？
～～～～～～～～～～～～～～～～～
店面，出了两道题，每道我都给出了两种解法，写出了code。
刚才feedback没有在第一时间给出最优解法，超时5分钟，要求加面。
我写code之前问，有两种解法，这样这样。都有利弊，利在哪，弊在哪。你要哪种？
对方说，随便。
然后我就写了。然后对方说，你没有第一时间给出最优解。
我说，大姐你让我随便的啊。再说都是O(n)啊。
然后对方说，我说过吗？ anyway， 在某些特殊情况下，第二种，要更快，所以你的解
不是最优解。
我说，“大姐，array.size()，的复杂度是O（n）啊！第二种方法，用了.size(),所以
复杂... 阅读全帖 |
|
发帖数: 1 | 14 问题：输入一个整数N，请问有多少种不同的方法把若干个连续的整数相加使得它们的
和为N？例如输入N=9，由于9 = 9、9 = 4 + 5、9 = 2 + 3 + 4，因此正确的输出是3。
分析：这是LeetCode第829题。
解法一：时间复杂度O(n)
我们可以想象有一个整数数组，数组里的第一个数字是1，第二个数字是2，以后的数字
以此类推。再假设有两个指针，第一个指针初始化指向数组的第一个数字，第二个指针
初始化指向数组的第二个数字。这两个指针就定位了一个子数组，该子数组由两个指针
之间的所有数字（包括两个指针指向的数字）组成。由于数组里的数字是连续递增的，
那么两个指针之间的任意子数组的数字也是连续递增的。
如果两个指针之间的子数组的所有数字之和小于输入的整数N，我们希望这个子数组包
含更多的数字，于是把第二个指针向右移动。每把第二个指针向右移动一位，相当于往
子数组的最右边添加一个新的数字，子数组的数字之和也会相应变大。如果此时子数组
的和仍然小于N，我们继续向右移动第二个指针。
如果子数组的和等于N，我们就找到了一个符合条件的子数组。接下来可以继续向右移
动第二个指针去寻找其... 阅读全帖 |
|
a**********0
发帖数: 422 | 15 interviewer的名字叫 Xusheng Sun
非常糟糕 不仅粗鲁无礼 喜欢抢话插话 而且技术很差 脑子不够用
按照约定的时间晚了很多 面试时间本来就不长 晚了既不解释也不道歉
问题问不到点子上 说个什么半天反应不过来
宝贵的面试时间竟然当场用来看我的简历 还看了很长时间 我还得保持安静让他把我的
简历看完 作为面试人 你早干什么去了
不停打断我说话 不停用很傻的 自以为有道理的问题challenge我 解释了他为什么是错
的 还是不停的put words into my mouth
（问题是serialize 的serialize 二叉树） 我说用level order traverse 他说指数复
杂度 必须用别的顺序的方式遍历
我解释复杂度是节点数目的线性函数 硬说是指数复杂度 也是树的高度的指数 但是如
果用其他方式遍历 同样的复杂度啊 做serialization难道不要把所有节点都遍历一边
任何顺序都要遍历一边 任何方式复杂度相同啊 这点都理解不了 而且我解释了好几遍
还理解不了 didi labs雇的人白痴啊
从来没有这么烂的面试经历 真的很烂 didi lab... 阅读全帖 |
|
l**n
发帖数: 7272 | 16 【 以下文字转载自 Automobile 讨论区 】
发信人: jamesgordon (高登大爷), 信区: Automobile
标 题: 丰田工程师真的该枪毙啊 (转载)
发信站: BBS 未名空间站 (Sun Nov 3 21:23:20 2013, 美东)
【 以下文字转载自 Auto_Fans 俱乐部 】
发信人: andrews (旱鸭子), 信区: Auto_Fans
标 题: 丰田工程师真的该枪毙啊
发信站: BBS 未名空间站 (Sun Nov 3 00:14:23 2013, 美东)
看下面的这文章，我是无语了……
以前不知道什么是＂在看不到的地方偷工减料＂， 这回见识了。 以后不敢买丰田车了
转贴自：http://club.tgfcer.com/thread-6817371-1-1.html 网友Kuzuryuusen的文章
----------------------------
【第一部分】背景简介
前几年闹得沸沸扬扬的丰田刹不住事件最近又有新进展。十月底俄克拉荷马的一次庭审
，2007年一辆2005年凯美瑞暴冲（Unintended Acceler... 阅读全帖 |
|
l**n
发帖数: 7272 | 17 【 以下文字转载自 Automobile 讨论区 】
发信人: jamesgordon (高登大爷), 信区: Automobile
标 题: 丰田工程师真的该枪毙啊 (转载)
发信站: BBS 未名空间站 (Sun Nov 3 21:23:20 2013, 美东)
【 以下文字转载自 Auto_Fans 俱乐部 】
发信人: andrews (旱鸭子), 信区: Auto_Fans
标 题: 丰田工程师真的该枪毙啊
发信站: BBS 未名空间站 (Sun Nov 3 00:14:23 2013, 美东)
看下面的这文章，我是无语了……
以前不知道什么是＂在看不到的地方偷工减料＂， 这回见识了。 以后不敢买丰田车了
转贴自：http://club.tgfcer.com/thread-6817371-1-1.html 网友Kuzuryuusen的文章
----------------------------
【第一部分】背景简介
前几年闹得沸沸扬扬的丰田刹不住事件最近又有新进展。十月底俄克拉荷马的一次庭审
，2007年一辆2005年凯美瑞暴冲（Unintended Acceler... 阅读全帖 |
|
b*****g
发帖数: 919 | 18 来自主题: BrainTeaser版 - 两个程序题 一. 已知一个有序递增数组.有n个元素.现在给一个数x,问这n个数里面是否存在两个数
,他
们的和为 x,假设都是整数. 要求, 时间复杂度为O(n),空间复杂度为O(1)...
二. 已知一个数组,有n个元素,要求找出它的一个子数组(必须是连续的元素),使得这个
子数
组各数之和为最大. 输出这个和即可. 要求,时间复杂度为O(n),空间复杂度为O(1)...
比如数组 3,8,-19,2,9,7,-6,10,-5,6,-7,1
找到了发现 2,9,7,-6,10,-5,6 是所求,只需要输出他们的和23即可 |
|
e*******a
发帖数: 53 | 19 ▲
你说“我不是很明白为什么“古代写书远远不够谋生，因为读者少，作者报酬少”所以
“当年罗贯中著《三国演义》、陈寿著《三国志》，所花费时间应该是少于甚至远少于
Martin写《冰与火之歌》””——你在对我的原话断章取义！把我的整段话连贯看，意
思浅显易懂，就是说Martin能够靠写《冰与火之歌》谋生，所以能专职写该书二十多年
，而罗贯中陈寿因为不能靠写《三国演义》《三国志》谋生，所以他们只能用谋生之余
的时间写三国，所以我得出结论“当年罗贯中著《三国演义》、陈寿著《三国志》，所
花费时间应该是少于甚至远少于Martin写《冰与火之歌》”，这有什么错吗？！我说得
如此明白，你“不是很明白”？！
▲
你说“而且就算花费的时间少，我也不明白为什么三国就比不上写了20年的东东布局简
单，谋略简单。”——首先，我认为Martin是和罗贯中陈寿同样级别的一时俊彦！
︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵︵
http://www.mitbbs.com/pc/pccon_12015_t0_234847.html
……我因一生看过太多小说，20年前就明白“作者智力决定书中... 阅读全帖 |
|
l*****8
发帖数: 16949 | 20 No. 2^N这样的复杂度通常称为EXP (exponential),或者叫指数复杂度。
P<=NP<=EXP.第一个可以去掉等号如果这个证明是正确的。但NP未必等于EXP.
P
NP
事实上这个一点都不明显。比如 PSPACE 和 NPSPACE就是相同的.也就是说如果只以占
用存储的大小来衡量复杂度的话，P和NP是相同的。通常我们说的P和NP是用时间来衡量
复杂度的。
另外，O(N)叫线形时间，多项式时间是O(N)+O(N^2)+O(N^3)+.....
2^N是exp问题。 |
|
f****8
发帖数: 33 | 21 楼上的算法复杂度为O(M^2*N^2).
下面给出O(M*N)的算法，以及实现。
第一步，先扫描各行各列，找出每一列1的个数，然后将每列1的个数及列号按个数从大
到小排列到
一个LIST中，且直接忽略1的个数小于50的列号；O(M*N)+O(MlogM)，其中N为行数，M为
列数。
第二步，根据第一步扫描的结果，创建 FP－tree（Frequency Pattern tree)。创建方
法如下：树中每个节点包括column-index,出现次数，worst复杂度O(M*N).
第三步，统计结果，就是遍历树的过程，有一些技巧，worst复杂度为O(M^2).
因为N》M，所以整体worst复杂度：O(M*N).
本人冬季刚计算机工程专业硕士毕业，之前在国内有一定工作经历，JAVA C++ WEB DB
都做过一些。找湾区码农工作，prefer涉及BIG DATA和MACHINE LEARNING相关的工作，
求内推：f****[email protected]，万分感激！ |
|
a***f
发帖数: 45 | 22 关键是要求是什么，是要求时间复杂度O(n)，还是空间复杂度O(1)？
空间复杂度要求O(1)的话好办，但要求时间复杂度O(n)就很难，在实际实现中用些毛招
还是可以做到的，就是理论上不完备。 |
|
n******t
发帖数: 4406 | 23 算法复杂度在简单的case里面比较一目了然。
复杂的情况下，时间复杂度都会受空间复杂度影响的。
Suffix tree就是个比较好的例子。
而且很多时候，需要的对象集是比较特殊的状况，
通用的算法复杂度也是没用的。 |
|
h*********n
发帖数: 11319 | 24 【 以下文字转载自 Automobile 讨论区 】
发信人: jamesgordon (高登大爷), 信区: Automobile
标 题: 丰田工程师真的该枪毙啊 (转载)
发信站: BBS 未名空间站 (Sun Nov 3 21:23:20 2013, 美东)
【 以下文字转载自 Auto_Fans 俱乐部 】
发信人: andrews (旱鸭子), 信区: Auto_Fans
标 题: 丰田工程师真的该枪毙啊
发信站: BBS 未名空间站 (Sun Nov 3 00:14:23 2013, 美东)
看下面的这文章，我是无语了……
以前不知道什么是＂在看不到的地方偷工减料＂， 这回见识了。 以后不敢买丰田车了
转贴自：http://club.tgfcer.com/thread-6817371-1-1.html 网友Kuzuryuusen的文章
----------------------------
【第一部分】背景简介
前几年闹得沸沸扬扬的丰田刹不住事件最近又有新进展。十月底俄克拉荷马的一次庭审
，2007年一辆2005年凯美瑞暴冲（Unintended Acceler... 阅读全帖 |
|
q*c
发帖数: 9453 | 25 别幻想了，物理上有能量守恒，信息上有复杂度守恒。 一件事物，有基本的复杂度，
无法通过人方式变得更简单， 你无非是个乾坤大挪移，把复杂度移动到不同的地方藏
起来。
抽象只是形势上化翻为简，实质的复杂度一点也无法减少，而且因为抽象增加了间接的
层次，其实变得更加的复杂。
抽象其实是增加了复杂密度，减少了表面积。 这玩意一点不简单。
哥就是物理专业的，各种复杂的物理现象抽象成简单的规律，看着简单吧？大部分人拿
着规律根本毫无办法应用， 因为地下的复杂情况一点没减少，你光抽象顶毛用。
你这样的小左来个空洞的理论到处忽悠，简单就是好，抽象就是简单，哈哈。 共产主
义世界真美好 |
|
c*********g
发帖数: 154 | 26 “Introduction of Algorithm”的“Medians and Order Statistics”有一个与之相
关的算法。
不过这道题M台计算机们各自为战，SELECT算法没法递归调用。假设数组的最大长度为N，那
么最坏情况下问题规模的递推公式大概是这样的：
T(nm)<=2T(n/2*m/2)+O(M)
其中O(M)在子问题中可以看做常数。由这个递推公式得到复杂度为O(sqrt(NM))。
但不要忘记，每个子问题都要做一遍O(M)，而子问题的个数有log_4(NM)个，所以这方
面的复杂度是log_4(NM)*O(M)。
两者综合考虑，最后的复杂度是O(sqrt(NM))。
还没有想到怎么做进一步的分析。感觉应该会有更好的算法使复杂度大概在O(NM*log(
NM))量级，即与排序算法一个量级。 |
|
s*******u
发帖数: 35 | 27 一个数的n次方需要（n-1） 个乘法实现，时间复杂度当然是O(n)；
zhou's book说递归算法时间复杂度是指数的，这个interviewer也同意，空间复杂度为
什么不同？
有谁解释的清楚点？压栈出栈的argument对时间和空间都适用的吗？我承认fibo有很好
的算法，但人家就是问递归的算法复杂度 |
|
c*********g
发帖数: 154 | 28 “一个数的n次方需要（n-1） 个乘法实现，时间复杂度当然是O(n)”，这是错误的，
因为四次方相当于平方的平方，只需两次计算。所以最好的时间复杂度是O(log(n))。
这也就是为什么fib最好效率能达到O(log(n))。
时间复杂度的分析就是看能把问题分解成怎样的小问题，写出递推式，然后求解。
Master Theory可以派上用场。
空间复杂度么，好像没有什么通用的方法，具体问题具体分析吧。 |
|
a*****s
发帖数: 6260 | 29 看下面的这文章，我是无语了……
以前不知道什么是＂在看不到的地方偷工减料＂， 这回见识了。 以后不敢买丰田车了
转贴自：http://club.tgfcer.com/thread-6817371-1-1.html 网友Kuzuryuusen的文章
----------------------------
【第一部分】背景简介
前几年闹得沸沸扬扬的丰田刹不住事件最近又有新进展。十月底俄克拉荷马的一次庭审
，2007年一辆2005年凯美瑞暴冲（Unintended Acceleration，UA）致一死一伤事件中
丰田被判有责。引起广泛关注的是庭审中主要证人Michael Barr的证词让陪审团同意丰
田的动力系统软件存在巨大漏洞可能导致此类事件。这是丰田在同类事件中第一次被判
有责。庭审过后丰田马上同意支付300万美元进入调解程序。
出于好奇，我漫不经心地下载了Barr的286页证词，却一下子被吸引住了。几天内读完
，算是对这次事件进行了一次深入了解。下面就从外行角度总结一下这份证词并尝试以
更简单的语言解释里面提到的暴冲原因以及丰田犯下的错误。
Barr的证词下载自他的个人博客Barr... 阅读全帖 |
|
z*n
发帖数: 2893 | 30
TM和NTM都是用来描述计算模型的，计算问题确定的前提下用两种不同
的计算模型会有不同的复杂度，计算理论研究的是不同的计算模型是否
等价和特定计算问题在不同计算模型中的复杂程度。
理论研究本身是不涉及什么虚拟存储，mp3 player, internet之类的工
程问题，用modem连接还是用fibre差的只是个常数，和TM混在一起谈是
笑话，就好象有人说P4比TM快一样。
数一个苹果和数地球上所有的苹果对于DFA来说都是常数问题，对于TM倒
成了O(N)问题了，你真行。
一般来说一种计算模型乘上个常数对于计算问题的复杂度是没有任何帮助的，
你的internet论就是这么个常数，不能降阶复杂度，所能解决问题的集合是
一样的。
至于智力是什么计算问题，谁都不知道，更不用说如何计算，计算复杂度，
用1台还是1万台机器算的问题了。 |
|
c***s
发帖数: 70028 | 31 作为一个生命，他卑微地、倔强地、孤独地活着，作为一个数学家，他应该伟大地、有尊严地、骄傲狂妄地活着。这个世界不仅需要一个生命，更需要让人类更光明的数学家。
——题记
数学家——白根弟，与数学家华罗庚颇有渊源，且有一个关于根号2背后的秘密。
2011年8月大运期间，我们发现了一位人士在深圳举办的世界大学校长论坛上向公众散发科普传单，上面写着有关数学危机引起的科学危机，导致人类面临重重危机的论述，算是科学最前沿的内容。他就是数学家白根弟。然而，没有得到多少回复，甚至“有不少校长表现得很不得体，好象他们大学与科学无关一样，却对政治有无限的兴趣”。这挫折使得白根弟倍感失望，但这并不影响他的自信，他表现得更像是一个天才，还是那样的超脱！
白根弟自信说，他很小就开始记忆，三岁就去放牛，很早就表现出在数学上的天赋，但没有遇到过什么名师指导。因为用“科学的发展与生物的发展是统一的”来证明“科学技术是第一生产力”，导师只给78分，使他没拿到学士学位。但丝毫不影响他写出成箱成箱的数学理论——四千多页《规则论》的稿纸，且在 80年代中寄到中科院，尽管被退稿（大部分遗失）……
白根弟在回顾数学探索之旅时动情地... 阅读全帖 |
|
z*******3
发帖数: 13709 | 32 玩游戏最重要一点就是ai不要当真
电脑是很难跟人脑比的
复杂度差太多，所以一般允许电脑作弊
因为电脑如果不作弊，你要人写出一个跟人脑竞争的ai
我的天，你看深蓝下个象棋都要上super computer
你搞个钢铁雄心，你觉得这个复杂度对比国际象棋来说
是高还是低？我觉得复杂度高太多了
如果要作出跟人脑竞争的ai，那supercomputer是必不可少了
还要一堆顶尖工程师陪着你搞，那谁有办法
还玩不玩游戏了？所以一般允许电脑自动暴兵这些
更不要说人玩的时候还可以s&l大法作弊
有本事你别作弊，战场上有时候连曼斯坦因和古德里安都会莫名其妙阵亡
然后调成双v难度，再试试
我之所以跑去玩钢铁雄心，就是因为看到有人说
用民国太难了，每次都被虐，所以建议远离钢铁雄心
后来发现，民国有瞬吞军阀的技巧，那难度就大幅下降了
至少我觉得钢铁雄心里面，对于东亚局势的描述，p社还是比较靠谱的 |
|
C********w
发帖数: 1724 | 33 一个深圳数学家的彷徨：国家为何不重视科学？
信源：天涯社区
数学家白根弟：“国家中长期科学规划”实质是反科学
作为一个生命，他卑微地、倔强地、孤独地活着，作为一个数学家，他应该伟大地、有
尊严地、骄傲狂妄地活着。这个世界不仅需要一个生命，更需要让人类更光明的数学家
。----题记
数学家----白根弟，与数学家华罗庚颇有渊源，且有一个关于根号2背后的秘密。
2011年8月大运期间，我们发现了一位人士在深圳举办的世界大学校长论坛上向公众散
发科普传单，上面写着有关数学危机引起的科学危机，导致人类面临重重危机的论述，
算是科学最前沿的内容。他就是数学家白根弟。然而，没有得到多少回复，甚至“有不
少校长表现得很不得体，好象他们大学与科学无关一样，却对政治有无限的兴趣”。这
挫折使得白根弟倍感失望，但这并不影响他的自信，他表现得更像是一个天才，还是那
样的超脱！
白根弟自信说，他很小就开始记忆，三岁就去放牛，很早就表现出在数学上的天赋，但
没有遇到过什么名师指导。因为用“科学的发展与生物的发展是统一的”来证明“科学
技术是第一生产力”，导师只给78分，使他没拿到学士学位。但丝毫不影响他写... 阅读全帖 |
|
l*****o
发帖数: 9235 | 34 码工要不停地写新算法，还要研究比较不同算法的时间复杂度和存储复杂度。
那你说说药剂师的工作有什么需要智商的地方？他们是要发明新药呢，还是要比较不同
用药的效果和复杂度啊？ |
|
E******w
发帖数: 2616 | 35 那是因为象棋复杂度不够。也许那个复杂度对人脑来说已经够了，人不可能算得很清楚
。但是对电脑不够。围棋的复杂度超过电脑死算的能力。电脑只会死算。所以算不清楚
就没有任何水平可言。 |
|
w********r
发帖数: 14958 | 36 刚google的就别在这现了。
PSPACE使空间复杂度，NP是时间复杂度。
无必然联系。 你丫连集合都搞不清楚。 A包含于B，说一个点属于B，不代表他只属于
B\A。PSPACE的问题的时间复杂度不代表一定大于NP |
|
l****o
发帖数: 832 | 37 我指的是非线性系统中复杂度。你的那个复杂度应该是cs里的算法复杂度，跟物理学里
的不是一个概念。
生物复杂不是一个细胞的概念就能说清楚的。首先细胞本身种类太多；其次，细胞是可
以产生湮灭的；再次，环境中非细胞的物质，比如各种大分子，无机分子，离子都是相
互作用的。
polynomial |
|
n*********a
发帖数: 1956 | 38 体制问题。
我又得说NP问题了，NP问题在随机过程input size小的时候就应该搞人治搞brute-
force魔鬼训练强奸解题法;
等input size大到一定程度门槛再这么搞霸王人治，那这个强奸党就得被自然规律掰断
小鸡鸡了。
看起来soccer,basketball,football,hockey这种team sports的组合复杂度的size就是
这个门槛，
跳水体操是input size小的运动，举国体制魔鬼训练可以长期有效。
soccer,basketball,football这些team sports的input size上升了一个数量级，组合
复杂度上升了不止一个数量级，再加上整个行业协会的运作复杂度上升了几个数量级，
出了魔鬼训练强奸党的掌控范围了(intractable)，搞人海战术估计效果不大，因为出
了魔鬼训练强奸党的掌控范围的所谓人海是一盘散沙。 |
|
c*****g
发帖数: 21627 | 39 【 以下文字转载自 IndustryParty 俱乐部 】
发信人: choming (请抵制“十万强插”计划！), 信区: IndustryParty
标 题: 揭秘4G核心专利
发信站: BBS 未名空间站 (Mon Jun 8 04:14:08 2015, 美东)
揭秘4G核心专利 (2015-03-03 19:30:02)
从2012年10月份决定写《通信之道》，到现在差不多两年半的时间，第一版终于成稿，
以此文作结。
3G霸主
1985年，在美国硅谷成立了一家叫Qualcomm(高通)的公司。 这家公司把军用的CDMA技
术用于民用通信，推出了IS-95标准，成为与欧洲的GSM竞争的第二代移动通信系统。
在第二代的商业竞争当中，GSM还是取得了的胜利。但是在高通公司的创始人当中有一
位世界级的科学家，叫做Andrew Viterbi，就是那位Viterbi译码算法的发明人，IEEE
Fellow，并获得了美国最高科技奖。在他的推动下，产业界相信了CDMA代表了无线通信
技术的发展方向，因此第三代移动通信的三个国际标准，WCDMA， CDMA2000和TD-SCDMA
都采... 阅读全帖 |
|
m*******e
发帖数: 1598 | 40 【 以下文字转载自 EE 讨论区 】
发信人: zhizunbao123 (你在红楼我在西游), 信区: EE
标 题: 怎样看待华为前工程师杨学志关于4G核心专利的看法？ (转载)
发信站: BBS 未名空间站 (Wed Jun 10 09:23:41 2015, 美东)
发信人: baodiao (钓鱼岛), 信区: PDA
标 题: 怎样看待华为前工程师杨学志关于4G核心专利的看法？
发信站: BBS 未名空间站 (Tue Jun 9 14:03:22 2015, 美东)
从网上看到一篇华为前工程师杨学志关于4G核心专利的看法， 不知各位有何高见？
当事人揭秘4G核心专利：高通没那么多，中国没那么少！
http://www.c114.net/news/41/a886875.html
1985年，在美国硅谷成立了一家叫Qualcomm(高通)的公司。这家公司把军用的CDMA技术
用于民用通信，推出了IS-95标准，成为与欧洲的GSM竞争的第二代移动通信系统。
在第二代的商业竞争当中，GSM还是取得了的胜利。但是在高通公司的创始人当中有一
位世界级的科学家，叫做Andrew V... 阅读全帖 |
|
Z****a
发帖数: 5434 | 41 游戏的复杂度和难度是两个概念。
复杂度到了一定程度，再增加复杂度并不会增加难度，只会让游戏更繁琐，降低可玩性。
国际象棋有10x10, 16x16 的变种。将棋还有20x20的。但是都没人要玩，因为太繁琐。 |
|
s********i
发帖数: 17328 | 42 这个说法只有部分道理，计算复杂度是很重要的概念，因为它直接涉及到处理时间。只
有当计算机处理的复杂度超过人类的处理时计算机才会赢。反过来讲，如果，计算机无
法处理的复杂度，人类也处理不了。 |
|
M**S
发帖数: 3483 | 43 增加一个对手并不等于计算复杂度上升，因为每一个对手是处于等同位置的，并且彼此
之间没有交流作弊的串联行为。电脑只需要对多出来的每一个对手多一套学习机制就可
以，是一个线性上升的计算复杂度，而由于人数上升牌堆未知牌下降造成的复杂度降低
则是一个非线性的下降，所以你的这个帖子基本暴露了你的知识水平。 |
|
M**S
发帖数: 3483 | 44 增加一个对手并不等于计算复杂度上升，因为每一个对手是处于等同位置的，并且彼此
之间没有交流作弊的串联行为。电脑只需要对多出来的每一个对手多一套学习机制就可
以，是一个线性上升的计算复杂度，而由于人数上升牌堆未知牌下降造成的复杂度降低
则是一个非线性的下降，所以你的这个帖子基本暴露了你的知识水平。 |
|
n**s
发帖数: 2230 | 45 楼上几位明显对计算复杂性理论不懂啊。围棋这种复杂度太高，是指数级的。计算机不
可能在有限时间内搜索全部可能，它的复杂度甚至远远高于我们最常见的NP-C问题。而
后者这类典型问题现在有5000多个，到现在也没有能解决。计算机速度再提高也没有用
，因为提高的速度是常数级的，解决不了指数级复杂度的问题。 |
|
S******r
发帖数: 4421 | 46 尼玛b sb的一个特征就是一个很清晰的概念 他给你复杂化
P问题的P指的就是多项式 也就是这个问题的复杂度可以用多项式表示。比如给你 x=
100个自然数，傻子也能在10000次比较以内排序好，这个复杂度就是x^2，这就是个多
项式，是P问题
NP指的是nondeterministic polynomial 指的是如果已经告诉你一个问题的答案 你可
以在多项式复杂度内断定答案的正确性 |
|
发帖数: 1 | 47 左起：查济民女儿，周光召，刘璧如，王小云，杨振宁，姚期智
来源 | 《数学文化》2019第10卷第2期
访问整理 | 王涛、王坤
昨天 （9月7日），2019年“未来科学大奖”数学与计算机科学奖宣布授予密码学
家王小云，奖励她在密码学领域的开创性贡献。王小云创造了一种毁灭性的密码分析方
法，破解了一个又一个国际通用的算法。那么，她的数学和密码人生是怎样展开的呢？
王小云，1966年出生于山东诸城，1981年进入诸城一中学习，1983年起就读于山东
大学数学系，先后获得学士、硕士、博士学位，师从潘承洞院士；1993年毕业后留校任
教，历任讲师、副教授、教授；2005年6月受聘为清华大学高等研究院“杨振宁讲座教
授”。现为第十三届全国人大代表、中国科协女科技工作者专门委员会委员、中国密码
学会副理事长、中国数学会常务理事。
王小云的主要研究领域为密码学。在密码分析领域，她系统给出了包括 MD5， SHA
-1 在内的系列 Hash 函数算法的碰撞攻击理论，提出了对多个重要 MAC 算法 ALPHA-
MAC、MD5-MAC 和 PELICAN 等的子密钥恢复攻击，以及 HMAC-MD5 的... 阅读全帖 |
|
x*****8
发帖数: 10683 | 48 米勒口味复杂度太单纯。
口味复杂度太高也不好喝，比如Corona Extra，永远像是放长了时间变坏的啤酒。
像札幌啤酒和Corona Light这样复杂度不高也不低最好。 |
|
y******e
发帖数: 1194 | 49 冷静，我有存档，你整理一下格式再发吧
————————————————————————————
背景简介
前几年闹得沸沸扬扬的丰田刹不住事件最近又有新进展。十月底俄克拉荷马的一次庭审
，2007 年一辆 2005 年凯美瑞暴冲（Unintended Acceleration，UA）致一死一伤事件
中丰田被判有责。引起广泛关注的是庭审中主要证人 Michael Barr 的证词让陪审团同
意丰田的动力系统软件存在巨大漏洞可能导致此类事件。这是丰田在同类事件中第一次
被判有责。庭审过后丰田马上同意支付 300 万美元进入调解程序。
出于好奇，我漫不经心地下载了 Barr 的 286 页证词，却一下子被吸引住了。几天内
读完，算是对这次事件进行了一次深入了解。下面就从外行角度总结一下这份证词并尝
试以更简单的语言解释里面提到的暴冲原因以及丰田犯下的错误。
Barr 的证词下载自他的个人博客 Barr Code，但现在该文已经被删除。（附在文末）
Michael Barr 是谁？他是一位拥有 20 年以上行业经验的嵌入式系统工程师。在十八
个月中，有 12 位嵌入式系统专家，包 Barr，受原... 阅读全帖 |
|
