【算法篇】时间复杂度与位运算

时间复杂度

通常使用最差的时间复杂度来衡量一个算法的好坏。

常数时间O(1)代表这个操作和数据量没关系,是一个固定时间的操作,比如说四则运算。

对于一个算法来说,可能会计算出如下操作次数 aN + 1N 代表数据量。那么该算法的时间复杂度就是O(N)。因为我们在计算时间复杂度的时候,数据量通常是非常大的,这时候低阶项和常数项可以忽略不计。

当然可能会出现两个算法都是O(N)的时间复杂度,那么对比两个算法的好坏就要通过对比低阶项和常数项了。


位运算

位运算在算法中很有用,速度可以比四则运算快很多。

在学习位运算之前应该知道十进制如何转二进制,二进制如何转十进制。这里说明下简单的计算方式:

  • 十进制 33 可以看成是 32 + 1 ,并且 33 应该是六位二进制的,因为 33 近似 32,而 32 是2的五次方,所以是六位,那么十进制 33 就是 100001 ,只要是2的此房,那么就是1,否则都为0
  • 二进制 100001 同理,首位是2^5,末位是2^0,相加得出 33

左移 <<

1
10 << 1 // -> 20

左移就是将二进制全部往左移动,10在二进制中表示为1010,左移一位后变为10100,转变为10进制也就是20,所以基本可以把左移堪称是 a * (2 ^ b)

右移 >>

1
10 >> 1 // -> 5

右移就是将二进制全部往右移动并去除多余的右边,所以右移等于 a / (2 ^ b)

右移很好用,比如可以用在二分算法取中间值

按位操作

按位与 &

每一位都为1,结果才为1

1
2
8 & 7
// 1000 & 0111 -> 0000 -> 0

按位或 |

其中一位为1,结果就是1

1
2
8 | 7
// 1000 | 0111 -> 1111 -> 15

按位异或 ^

每一位都不同,结果才为1

1
2
3
4
5
8 ^ 7
// 1000 ^ 0111 -> 1111 -> 15

8 ^ 8
// 1000 ^ 1000 -> 0000 -> 0

从以上代码中可以发现按位异或就是不进位加法

两个数不使用四则运算得出和

这道题中可以按位异或,因为按位异或就是不进位加法, 8 ^ 8 = 0,如果进位了,就是16了,所以我们只需要将两个数进行异或操作,然后进位。那么也就是说两个二进制都是1的位置,左边应该有一个进位1,所以可以得出以下公式 a + b = (a ^ b) + ((a & b) << 1) ,然后通过迭代的方式模拟加法。

1
2
3
4
5
6
7
function sum(a, b){
if(a == 0) return b
if(b == 0) return a
let newA = a ^ b;
let newB = (a & b) << 1;
return sum(newA, newB);
}
坚持原创技术分享,您的支持将鼓励我继续创作!