算法复杂度初探

发表于 分类于
学习笔记

翻译

algorithm complexity: 算法复杂度

示例

[3, 2, 1, 5, 7]中, 最大的数字是多少

1
2
3
4
5
6
7
8
9
public int max(int[] nums) {
    int ans = nums[0];
    for (int i : nums) {
        if (i > ans) {
            ans = i;
        }
    }
    return ans;
}

T(n)=O(n)
T(n)表示次数, O(n)表示时间复杂度

线性阶(Linear)

上述的这种叫做线性阶
在一个长度为n的范围内, 我们只需要查找他的一半,
则

因为2为常量, 因此可以去除, 即:

常数阶(Constant)

O(1)常数阶
s(n)=1+2+3+…+n=n(n+1)/2

对数阶(Logarithmic)

O(log2 n)对数阶(以2为底n的对数)
二分查找
在0~8之间查找某个数字, 例如7, 至多会查找3次

推导: 16查找多少次(4), 128查找多少次(7)

平方阶(quadratic)

O(n^2)平方阶
1,2,3三个数字总共有多少个组合?
[1,2],[2,3],[1,3]
[2,1],[3,2],[3,1]
推导公式为n*(n-1), 去除重复组合部分为

对一组数字进行升序排序,
[3,4,2]
3比4—>[3,4,2]
3比2—>[2,4,3]
4比3—>[2,3,4]
对一个N位的数组, 设两个数字i,j进行比较
i=nums[n];
j=nums[n-1],nums[n-2]….n;

推导公式如下

2和1都是常量, 因此舍弃, 即
O(n²)

类似的还有O(n³)立方阶(cubic), 线性对数阶O(n log2n)…，
k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。