【数据结构与算法】复杂度知识

什么是算法?

算法是用于解决特定问题的一系列的执行步骤。

以下算法是为了解决两数相加的问题。

// 计算a和b的和
public static int plue(int a, int b){
    return a + b;
}

以下算法是为了解决 n个数字的和 的问题。

// 1+2+3+...+n
public static int sum(int n){
    int result = 0;
    for(int i = 1; i <= n; i++){
        result += I;
    }
    return result;
}

使用不同算法,解决同一个问题,效率可能相差非常大。
比如:求第 n 个斐波那契数(fibonacci number)

如何评判一个算法的好坏?

如果单从执行效率上进行评估,可能会想到这么一种方案:

比较不同算法对同一组输入的执行处理时间
这种方案也叫做:事后统计法
上述方案有比较明显的缺点:

执行时间严重依赖硬件以及运行时各种不确定的环境因素
必须编写相应的测算代码
测试数据的选择比较难保证公正性
一般从以下维度来评估算法的优劣:

正确性、可读性、健壮性(对不合理输入的反应能力和处理能力)
时间复杂度(time complexity)
估算程序指令的执行次数(执行时间)
空间复杂度(space complexity)
估算所需占用的存储空间
由于现在硬件发展的较好,一般情况下我们更侧重于时间复杂度。

大O表示法(Big O)

一般用大O表示法来描述复杂度,它表示的是数据规模 n 对应的复杂度。

忽略常数、系数、低阶:

9 >> O(1)
2n + 3 >> O(n)
n2 + 2n + 6 >> O(n2)
4n3 + 3n2 + 22n + 100 >> O(n3)
写法上,n3 等价于 n^3
注意:大O表示法仅仅是一种粗略的分析模型,是一种估算,能帮助我们短时间内了解一个算法的执行效率。

对数阶的细节

对数阶一般省略底数

log29 ∗ log9n >> log2n
所以 O(log2n) 、O(log9n) 统称为 O(logn)

常见的复杂度

20200326125216195.png
20200326125550303.png
20200326125519876.png

多个数据规模的情况

时间复杂度:O(n + k)

public static void test(int n, int k){
    for(int i = 0; i < n; i++){
        System.out.println("test");
    }
    for (int i = 0; i < k; i++){
        System.out.println("test");
    }
}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。