对于我们在算法分析中遇到的大多数复杂性,我们通常只有一个单词:
O(1) =="常数"O(log n) =="对数"O(n) =="线性"O(n^2) =="二次"O(n^3) =="立方"O(2^n) =="指数"我们遇到O(n log n)具有一定规律性的复杂算法(想想所有算法都以排序复杂性为主)但据我所知,我们在英语中没有一个单词能用来指代那种复杂性.这是我的知识差距,还是我们关于计算复杂性的英语话语中的真正差距？
我今天早些时候正在享受"The Humble Programmer"并且遇到了这个选择报价:
因此,就目前而且可能永远而言,第二类规则本身就是程序员所要求的学科要素.我想到的一些规则是如此清晰,以至于它们可以被教导,并且永远不需要就某一特定程序是否违反它们进行争论.例如,在没有提供终止证明的情况下也不应写下循环,也不说明不会因执行可重复语句而破坏其不变性的关系.
我正在寻找Dijkstra的1300多篇着作中哪一篇最能详细描述,如上所述.
我正在阅读DJB的"关于Qmail 1.0十年后安全性的一些想法",他列出了这个函数用于移动文件描述符:
int fd_move(to,from)
int to;
int from;
{
if (to == from) return 0;
if (fd_copy(to,from) == -1) return -1;
close(from);
return 0;
}
我突然想到这段代码没有检查close的返回值,所以我读了man页面close(2),看起来它可能会失败EINTR,在这种情况下,适当的行为似乎是再次调用close用同样的论点.
由于这段代码是由在C和UNIX上经验丰富的人编写的,并且在qmail中已经保持了十多年不变,我认为必须有一些我缺少的细微差别才能使这段代码正确.任何人都可以向我解释这种细微差别吗？
相关链接:http://en.wikipedia.org/wiki/Hopscotch_hashing
跳房子哈希表似乎很棒,但我没有在文献中找到这个问题的答案:如果我的邻居大小为N并且(由于渎职或运气极差)会发生什么？我插入N + 1个元素,这些元素都是哈希同样的确切值？
hash hashtable hash-collision data-structures hopscotch-hashing