算法时间复杂度和空间复杂度简介-526互联

评估算法的核心指标

1 时间复杂度

2 空间复杂度

空间复杂度就是算法解决一个问题时额外占用的内存空间是多大

时间复杂度就是算法解决一个问题时数据量和运行时间的关系

一般我们评判算法的优劣首先考虑的就是时间复杂度。

时间复杂度

什么是常数时间操作？

执行时间固定的就是常数时间操作，和样本量大小没有关系

例如:

1+1和 43241234+4123151235 的执行时间是固定的

常见的常数时间操作

算术运算：+, -, *, /, %

位运算：>>, >>>, <<, |, &, ^

赋值、比较、自增、自减

数组寻址操作

时间复杂度怎么估算？

充分理解算法流程
拆分算法流程：拆分出来的行为都是常数时间的操作
找到数据量和常数操作的关系是什么，建立表达式
完成表达式建立后，只取最高阶，低阶向都去掉，低阶的系数也去掉

记为：O(忽略系数的高阶项)

为什么用big O？

看了一圈大家都比较赞同的是big O 好写，而Θ ，Ω 键盘上没有

常见时间复杂度从好到差

O(1) 常数时间

O(logN)

O(N)

O(N*logN)

O(N^2)...O(N^K)

O(2N)...O(KN) 递归

O(N!) 最差

选择排序的时间复杂度估算

一个数组arr，有N个数，对arr进行选择排序

实现思路：

arr[0...N-1]范围上，找到最小值所在的位置，把最小值交换到0位置

arr[1...N-1]范围上，找到最小值所在的位置，把最小值交换到1位置

arr[2...N-1]范围上，找到最小值所在的位置，把最小值交换到2位置

...

arr[N-1..N-1]范围上，找到最小值所在的位置，把最小值交换到N-1位置

代码：

    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 0 ~ N-1  找到最小值，在哪，放到0位置上
        // 1 ~ n-1  找到最小值，在哪，放到1 位置上
        // 2 ~ n-1  找到最小值，在哪，放到2 位置上
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) { // i ~ N-1 上找最小值的下标 
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }