时间复杂度问题

发布： 分类： 评论： 阅读：

时间复杂度

一遍循环：O(n)

嵌套两遍循环：O(n*n)

1
2
3
for(int i=0;i<n;i++) 
    for(int j=0;j<n;j++)
        .....

O(log n) 与 O(n log n) 分析方法：

📍 自理解：一般这种带有 logn 都是有递归操作的。例如二分查找，就是每次我找到中间位置，然后如果查找的值大于当前值，那么我只需在后一半中继续查找，如果查找的值小于当前值，就在前一半中继续查找，每次我都可以减少一半数量的元素。其时间复杂度为 O(logn) 。像归并排序, 虽然我每次把整个array分成了两个部分，但是两个部分都需要去进行递归处理，那么时间复杂度就是 O(nlogn) 。

📍 通过递归深度来计算时间复杂度：

快速排序的时间复杂度：快速排序是通过交换，找到中间位置的元素，然后左右两部分分别去递归进行排序。

如上图所示，如果快排每次选的节点恰好为中间节点，也就是二叉树是平衡的，那么二叉树的深度为 log(n+1) ，而在遍历每一层的时候，n个节点都会访问到。如上图 B 和 C 节点，虽然递归后不是一次访问n个节点，B 和 C 两次递归加起来就是总的节点个数n，一共有 log(n+1) 层，所以其时间复杂度为 O(n*log(n+1)) = O(nlogn)

二分查找的时间复杂度： 二分查找是每次访问中间节点，判断中间节点和我们要找的节点之间的大小，如果中间节点大于目标节点，那么只访问左半部分，否则只访问右半部分。

如上图所示，二叉树的深度为 log(n+1) ，先访问递归 A, 如果目标节点大于当前值 ，那么访问递归 C， 如果目标节点小于当前值，那么访问递归 F， 如果目标节点小于当前值，那么访问递归 L。从这个路径来看，在每一层的递归时，只需要访问一个节点，其时间复杂度为 O(1) 。二叉树的深度为 log(n+1) ， 所以二分查找的时间复杂度为 O(1*log(n+1)) = O(logn)

在未排序数组中寻找第k大的数的时间复杂度：寻找第k大的数，利用的是快速排序的思想，经过一轮排序，我们会找到一个元素的最终位置index，如果k大于index，那么我只要在后面继续快排，如果k小于index，那么就在前面快排。它和快排的区别在于我只要在一半的部分进行快排即可，而不需要两侧都进行快排。

如上图所示，二叉树的深度为 log(n+1) ，

  • 在第一层时，n 个节点都需要被访问到。
  • 如果 k 大于 index，那么执行 C 侧的递归即可，这时需要访问的节点数为 n/2。
  • 如果 k 大于 index，那么执行 G 侧的递归即可，这时需要访问的节点数为 n/4。
  • 二叉树的深度为 log(n+1) ， 那么一共需要：$$n + \frac{n}{2} + \frac{n}{4} +…+ \frac{n}{2^{log(n+1)-1}} = \frac{2n^2}{n+1} = O(n)$$

相关例题

leetcode 169. 找出数组中出现次数大于一半的元素

1
2
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
  • 统计一遍。O(n)， 但需要额外的空间保存每个数字出现的次数。
  • 排序。因为该元素出现次数大于一半，也就是说，排序后中间位置的数字一定是出现次数大于 ⌊ n/2 ⌋ 的元素。而排序的时间复杂度最少也为O(nlogn).
  • 排序后，中间的数字一定是出现次数大于 ⌊ n/2 ⌋ 的元素，也就是说我们只要找到排序后的中间元素就好了。这道题就可以转换为：找出第n/2大的数。
  • 哈哈，这样就可以利用快排的特点了，那么就可以把时间复杂度缩小到O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int partition(int[] nums, int begin, int end) {
    int tmp_value = nums[begin];
    while(begin<end) {
        while(begin<end && nums[end]>=tmp_value) end -= 1;
        if(begin < end) nums[begin] = nums[end];
        while(begin<end && nums[begin]<=tmp_value) begin += 1;
        if(begin < end) nums[end] = nums[begin];
    }
    nums[begin] = tmp_value;
    return begin;
}

public int majorityElement(int[] nums) {
    int index = 0, begin = 0, end = nums.length-1;
    while(index!=nums.length/2) {
        index = partition(nums, begin, end);
        if(index>nums.length/2) end = index-1;
        else if(index<nums.length/2) begin = index+1;
    }
    return nums[index];
}

剑指offer. 找出数组中最小的k个数

  • 方法一：和上面一样，利用二分查找，找到最小的k个数，那么只要找到第k+1大的数，那么他之前的就是最小的k个数。这种方式会改变数组内的值
  • 方法二：不改变数组的值。设置一个容器，存储空间为k，遍历数组，每遍历到一个数，判断容器里的最大值和当前值大小，如果当前值小于容器中的最大值，删除容器中的最大值，用当前值替换。
  • 而在容器中找到最大值插入删除的操作，最省时的是构建最大堆。时间复杂度为O(log k)。那么总的时间复杂度就是O(n log k)
  • 第二种方法对海量数据很有用，因为第一种方法需要一次把所有的数据都读进来，而第二种方法可以一个一个读入，辅助空间为k即可。n很大k很小时，这种方法很好。
1

剑指offer. 在排序数组中查找某数字出现的次数

  • 利用二分查找，找到重复数字的左右端点。
  • 查找左端点的时候，利用二分查找，如果当前节点为重复数字，看它和左边的节点是否相等，如果不相等，那么该节点为左端点。 右端点也是一样的。
  • 找到左右端点的位置，就可以知道其出现次数了
1

剑指offer. 0到n-1中缺失的数字

1
长度为n-1的递增序列，其中只有一个数字不存在。找到这个不存在的数字。
  • 就是找到第一个index与值不相等的元素。
  • 二分查找 。如果当前值和index不等，并且前一个值和index相等，那么这个值就是我们想要的。

剑指offer. 递增序列，找到值与index相等的任意一个元素。

  • 如果当前值比index小，那么它前面不可能有了，只能向后找
  • 如果当前值比index 大，那么它后面是不可能有了，只能向前找。
1

把数字翻译成字符串。

p 231. 46题

1

leetcode 4. 找到两个已排序数组的中位数

  • 最简单直接的方法，先将两个有序数组合并成一个有序数组，然后找到中位数。
  • 合并时可以到 (nums1.length + nums2.length)/2 + 1 的时候就停止，因为我们的目的就是找中位数。
  • 这种方法的时间复杂度是 O(m+n) 。 m 和 n 分别为两个数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public int[] merge(int[] nums1, int[] nums2) {
    int length = nums1.length + nums2.length;
    int[] res_arr = new int[length];
    if(nums1.length==0) res_arr = Arrays.copyOf(nums2, nums2.length);
    else if(nums2.length==0) res_arr = Arrays.copyOf(nums1, nums1.length);
    else {
        int begin_1 = 0, begin_2 = 0;
        for(int i=0;i<length;i++) {
            if(begin_1>=nums1.length) {
                res_arr[i] = nums2[begin_2];
                begin_2 += 1;
            }
            else if(begin_2>=nums2.length) {
                res_arr[i] = nums1[begin_1];
                begin_1 += 1;
            }
            else {
                if(nums1[begin_1]<nums2[begin_2]) {
                    res_arr[i] = nums1[begin_1];
                    begin_1 += 1;
                }
                else {
                    res_arr[i] = nums2[begin_2];
                    begin_2 += 1; 
                }
            }
            if(i==length/2+1)
                break;
        }
    }
    return res_arr;
}

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int length = nums1.length + nums2.length;
    int[] res = merge(nums1, nums2);
    if(length%2==0) return (res[length/2-1] + res[length/2])/2.0;
    else return res[length/2];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if(nums2.length<nums1.length) { //为了让nums1中存的是短的数组
        int[] tmp = nums1;
        nums1 = nums2;
        nums2 = tmp;
    }
    int begin = 0;
    int end = nums1.length;
    int length = (nums1.length + nums2.length + 1)/2;

    while(begin<=end) {
        int mid1 = (begin + end)/2;
        int mid2 = length - mid1;
        if(mid1<nums1.length && nums2[mid2-1]>nums1[mid1]) {
            begin = mid1 + 1;
        }
        else if(mid1>0 && nums1[mid1-1]>nums2[mid2]){
            end = mid1 - 1;
        }
        else {
            int max_of_left = 0;
            if(mid1==0) max_of_left = nums2[mid2-1];
            else if(mid2==0) max_of_left = nums1[mid1-1];
            else max_of_left =  Math.max(nums1[mid1-1], nums2[mid2-1]);

            if((nums1.length + nums2.length)%2==1) return max_of_left;

            int min_of_right = 0;
            if(mid1==nums1.length) min_of_right = nums2[mid2];
            else if(mid2==nums2.length) min_of_right = nums1[mid1];
            else min_of_right =  Math.min(nums1[mid1], nums2[mid2]);

            return (max_of_left + min_of_right)/2.0;
        }
    }
    return 0;
}

leetcode 380. O(1)时间插入、删除、随即抽取

1
2
3
4
Design a data structure that supports all following operations in average O(1) time.
1. insert(val): Inserts an item val to the set if not already present.
2. remove(val): Removes an item val from the set if present.
3. getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
  • O(1)时间进行插入和删除操作，也就是不能遍历。
  • 而且不能删除list中间的某一个元素，因为删除list中间的某一个元素的时间复杂度是O(n), 因为后面的元素需要全部向前面移动一位，也就是如果要使用list，那么只能删除最后一个元素。
  • 可以使用hashmap，因为hashmap相当于链表，这道题又是set，也就是不存在重复元素。但是因为最后要随机抽取元素，只用map也不行，因为随机一个index之后，不能在map中去遍历，因为时间复杂度需要是O(1).
  • 所以只能map和list一起用，map中存储元素值和其在list中的索引，每删除一个元素，那么我们需要把list中的最后一个元素和当前元素交换，然后删除最后一个元素。并且改变map中最后一个元素的value值，也就是在list中的索引值。这样随机取数的时候只要在list中get(index)即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

class RandomizedSet {
    // map里面存储值和该值在list种的索引
    private Map<Integer, Integer> map;
    private ArrayList<Integer> list;

    // Initialize your data structure here. 
    public RandomizedSet() {
        map = new HashMap();
        list = new ArrayList();
    }
    
    // Inserts a value to the set. 
    // Returns true if the set did not already contain the specified element. 
    public boolean insert(int val) {
        if(map.putIfAbsent(val, list.size())==null) {
            list.add(val);
            return true;
        }
        return false;
    }
    
    // Removes a value from the set. 
    // Returns true if the set contained the specified element.
    public boolean remove(int val) {
        int index = map.getOrDefault(val, Integer.MAX_VALUE);
        if(index==Integer.MAX_VALUE) return false;
        else {
            map.remove(val);
            if(index<list.size()-1) {
                // 用list中的最后一个元素替换该位置的值
                list.set(index, list.get(list.size()-1)); 
                // 改变map中该元素对应的value值，即其在list中的索引
                map.put(list.get(list.size()-1), index); 
            }
            list.remove(list.size()-1); // 删除list中的最后一个元素
            return true;
        }
    } 
    
    // Get a random element from the set. 
    public int getRandom() {
        int p = (int)(Math.random()*(list.size()));
        return list.get(p);
    }
}

leetcode 381. O(1)时间插入、删除、随即抽取 (允许重复)

1
2
3
4
Note: Duplicate elements are allowed.
1. insert(val): Inserts an item val to the collection.
2. remove(val): Removes an item val from the collection if present.
3. getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.