[数据结构] 算法的效率（时间复杂性和空间复杂性） - V．oj 习题的复杂性

1.消失的数字

面试题 17.04. 消失的数字 - 力扣（LeetCode）

思路1：

先排序，在依次查找，如果下一个值不等于前一个+1，下一个值就是消失的数字。

经过计算，程序一共执行了N^2+N次，时间复杂度是O(N^2)。 

思路2：

先求和0-N，在依次减去数组中的值。

 经过计算发现，程序执行了2*N次，时间复杂度为O(N)。

思路3：

异或。

基本操作执行最好1次，最坏O(logN)次，时间复杂度为 O(logN)。

2.轮转数字

189. 轮转数组 - 力扣（LeetCode）

思路1：

暴力求解。

 基本操作执行最好0次，最坏O(N*k)次，时间复杂度为 O(N*k)。

思路2：

三段逆置

 经过计算发现，程序执行了2*N次，时间复杂度为O(N)。