PDF《数据结构与算法（DSA）》

偶数'

: '

奇数'

;

3. } 4. console.log(isEvenOrOdd(10)偶数 5. console.log(isEvenOrOdd(10001)奇数 你也可以用位操作符:n&

1 来代替 n%2(想想为什么可以代替?);

不管你输 入的是

10 还是 10001,第二行也只执行一次. 注意:不是说因为这个函数的代码只有

1 行,所以他的时间复杂度是 O(1),你要根据它 的具体实现去分析. 如果你使用 Array.sort()或者其他数组或者对象的方法,你必须查看它的代 码实现才能确定其时间复杂度(虽然 Array.sort()只有一行,但可能它的内部实 现有几十甚至上百行代码) 编程语言中的一些原始操作, 如加、减、乘、除、求余、位移等操作的时间 复杂度都为 O(1) , 这其实是很了不起的实现 ;

如果你按照教科书上的乘法规则去计算两个很大的数字相乘,它的时间复杂 度会是 O(n?),所以这里说的原始操作,其实是指在编程语言所限定的最小值和最 大值(比如,在JS 语言中: Number.MAX_VALUE 的大小是 1.7976931348623157e+308)范围内进行的操作.对于大数相乘,其实有比 O(n?)更优的算法,有兴趣的可以百度:Karatsuba 算法 这个例子非常简单,让我们来看另外一个例子 字典内查找值 根据单词获取它出现的次数 1. const dictionary = {the: 15, be: 125, and: 173, of:

15 2. function getWordFrequency(dictionary, word) { 3. return dictionary[word];

4. } 5. console.log(getWordFrequency(dictionary, '

the'

));

6. console.log(getWordFrequency(dictionary, '

of'

));

译者注:上图代码与原文代码有些许改动,仅是为了让代码更加简短,方便阅读,并不影响原 文作者想要表达的内容 同样,我们可以确定,即使字典有

10 个或者

100 万个单词,它依然只执 行第

3 行来查找单词.所以它的时间复杂度是 O(1).然而,如果我们是用数组而 不是哈希表来存储这个字典数据的时候,那么它会有很不一样的结果.下一节, 我们将讨论在数组中查找某个元素的时间复杂度 拥有最完美的哈希函数的哈希表,才会有最差时间复杂度都为 O(1)的情况.构造最完 美的哈希函数是不切实际的,因为哈希函数不可避免的出现键冲突,为了解决冲突,就会 导致最差时间为 O(n)的情况;

但是平均来说,哈希表查找的时间复杂度仍是 O(1) O(n)线性时间复杂度 线性时间复杂度算法是很常见的,它意味着在最坏的情况下会遍历输入的每 个元素 线性时间复杂度意味着随着输入的增长,算法按比例需要更长的时间来完 成.具有线性时间复杂度的算法一般记为:O(n), 让我们来看一个例子 从未排序的数组中查找最大值 假设你想从一个未排序的数组中找到最大值 1. function findMax(n) { 2. let max;

3. let counter = 0;

4. for (let i = 0;

i <

n.length;

i++) { 5. counter++;

6. if(max === undefined || max <

n[i]) { 7. max = n[i];

8. } 9. } 10. cons........