前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【数据结构与算法】什么是时间复杂度和空间复杂度?

【数据结构与算法】什么是时间复杂度和空间复杂度?

作者头像
村雨遥
发布2022-06-15 10:09:02
1990
发布2022-06-15 10:09:02
举报
文章被收录于专栏:JavaPark

前言

所谓算法,其实就是我们用来操作数据、解决程序问题的一组方法。针对同一个问题,我们可以采用不同的算法,然后实现相同的结果。但是针对不同的算法,对于时间和资源的消耗却有不同的差别。而为了分析不同算法的效率,我们常常从 时间空间 两个方面来对比,然后从中挑出最适合我们的解决方案。

本文主要从时间复杂度和空间复杂度的定义说起,然后介绍常见的时间复杂度和空间复杂度,最后则是对常见排序算法进行了总结。

时间复杂度

定义

分析时间复杂度的方法

总结起来,对于如何分析一段代码的时间复杂度,主要有如下 3 个实用方法:

  1. 只关注循环执行次数最多的一行代码;
  2. 加法原则:总复杂度等于量度最大的那段代码的复杂度;
  3. 乘法原则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见的时间复杂度曲线

常见时间复杂度

代码语言:javascript
复制
void sayHello(String name){
    System.out.prinln("Hello, " + String);
    System.out.prinln("欢迎关注我的公众号:【村雨遥】");
}
代码语言:javascript
复制
int binarySearch(int[] arr, int target){
    int left = 0;
    int right = arr.length - 1;
    while(left <= right){
        int middle = left + (left - right) / 2;
        if(arr[middle] == target){
            return middle;
        }else if(arr[middle] > target){
            right = middle - 1;
        }else {
            left = middle + 1;
        }
    }

    return -1;
}
代码语言:javascript
复制
int sum(int[] arr){
    int total = 0;

    for(int i = 0; i < arr.length; i++){
        total += arr[i];
    }

    return total;
}
代码语言:javascript
复制
void hello (int n){
    for( int i = 1 ; i < n ; i++){
        int m = 1;
        while( m < n ){
            m *= 2;
        }
    }
}
代码语言:javascript
复制
void selectionSort(int[] arr, int n){
    for(int i = 0; i < n; i++){
        int min = i;
        for(int j = i + 1; j < n; j++){
            if(arr[j] < arr[min]){
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}
代码语言:javascript
复制
void demo(int n){
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                System.out.print("Hello, World");
            }
            System.out.print("------");
        }
        System.out.print("******");
    }
}

空间复杂度

定义

常用空间复杂度

代码语言:javascript
复制
int num1 = 1;
int num2 = 2;
int total = num1 + num2;
代码语言:javascript
复制
int[] arr = new int[n];
代码语言:javascript
复制
int[][] arr = new int[n][n];

常见排序算法的时间复杂度和空间复杂度

对于面试中常见的的排序算法,以下总结给出了其时间复杂度以及空间复杂度,以及算法稳定性。

总结

好了,以上就是今天文章的内容了。主要介绍了时间复杂度的定义、推导原则以及常见时间复杂度,还对空间复杂度定义以及常见空间复杂度进行了介绍,最后则是总结了常见排序算法的时间复杂度和空间复杂度。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020-06-26,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 时间复杂度
    • 定义
      • 分析时间复杂度的方法
        • 常见的时间复杂度曲线
          • 常见时间复杂度
          • 空间复杂度
            • 定义
              • 常用空间复杂度
              • 常见排序算法的时间复杂度和空间复杂度
              • 总结
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档