聊一聊什么是算法复杂度

1.什么是算法？

回答：算法是用于解决特定问题的一系列操作步骤

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

//计算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）
    ps.不知道什么叫斐波那契数的可以自行百度

2.如何判断一个算法的好坏

  • 举个栗子：
    同样是计算1+2+3...+n的和
    有下面两种方法
public static int sum1(int n){
     int result = 0;
     for (int i = 1;i <= n; i++){
          result += I
    }
    return result
}

public static int sum2(int n){
   return (1 + n) * n / 2
}

明显可以只管的看出sum2 肯定比sum1 的执行效率要好，但是判断一个算法的好坏并不是靠直观的感受来判断的，它有自己的一套量化标准，我们叫算法复杂度。

单从执行效率进行评估，可能会想到那么一种方案

  • 比较不同算法对同一组输入的执行处理时间
  • 这种方案叫做：事后统计法

但是这种方案有比较明显的缺点

  • 执行时间严重依赖硬件及运行时各种不确定的环境因素
  • 必须编写相应的测算代码
  • 测试数据的选择比较难保证公正性

我们一般从以下维度来评估算法的优劣

  • 正确性，可读性，健壮性（对不合理的输入的反应能力和处理能力）
  • 时间复杂度（time complexity）:估算程序指令的执行次数（执行时间）
  • 空间复杂度（space complexity）:估算所需要占用的存储空间

复杂度的量化单位 ->大0表示法（Big 0）

  • 一般用大O 表示法来描述复杂度，他表示的数据规模n对应的复杂度

举个栗子：

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

函数sum 的执行指令的次数为 2 + n (我们认为一行代码的执行就是一次计算机指令的执行) 但是在算法复杂度的计算中我会将产生直接忽略掉不管这个常数是2 还是 200000。所以sum函数的时间复杂度我们用大O表示法来表示就是 O(n)

对数阶细节

  • 套用换底公式可以得出
    log2n = log29 * log9n
    由于log29是一个很小的常数 所以在计算算法复杂度时可以认为 log2n 与log9n是相 等的。从而可以用log2n表示所有的log级别的复杂度统称为logn

常见的复杂度

常见的复杂度
复杂度变化图小数据
复杂度变化图大数据
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容