不了解时间空间复杂度,别说你是程序员!!!

简介: 不了解时间空间复杂度,别说你是程序员!!!

前言

前几天面试了几位java开发人员先不说算法如何,竟然都不知道时间复杂度和空间复杂度。下面我讲一讲什么是时间复杂度和空间复杂度吧。

2 时间复杂度

定义

一般情况下,算法中 基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等 于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 ),简称时间复杂度。

如何推导出时间复杂度有以下原则

  • 如果运行时间是常数量级,则用常数1表示
  • 只保留时间函数中的最高阶项
  • 如果最高阶项存在,则省去最高阶项前面的系数

举例说明

T(n) = O(1),执行次数是常量

void dome1(int n) {
    System.out.println("你好");
}

T(n) = O(logn),执行次数是对数

void dome3(int n) {
    for (int i = n; i > 1; i /= 2) {
        System.out.println("你好");
    }
}

T(n) = O(n),执行次数是线性

void dome2(int n) {
    for (int i = 0; i < n; i++) {
        System.out.println("你好");
    }
}

T(n) = O(n²),执行次数是多项式

void dome4(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            System.out.println("你好");
        }
    }
}

总结

随着n的增长,那个需要的时间最长呢?

O(1) < O(logn) < O(n) < O(n²),当然时间复杂度不止这些,上面只是取了常用的来说明。

下面给出一张表自己体会下:
640.jpg

空间复杂度

定义

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。

S(n) = O(1),存储空间固定

void dome1(int n) {
    int i = 3;
}

S(n) = O(n),线性空间

void dome2(int n) {
    int[] i = new int[n];
}

S(n) = O(n²),二维空间

void dome3(int n) {
    int[][] i = new int[n][n];
}

总结

随着n的增长,那个需要的空间最大呢?

O(1) < O(n) < O(n²),当然空间复杂度不止这些,上面只是取了常用的来说明。

时间与空间的关系

对于一个算法,其时间复杂度和空间复杂度往往是相互影响的。当追求一个较好的时间复杂度时,可能会使空间复杂度的性能变差,即可能导致占用较多的存储空间;反之,当追求一个较好的空间复杂度时,可能会使时间复杂度的性能变差,即可能导致占用较长的运行时间。所以在很多时候,我们不得不在时间复杂度和空间复杂度之间进行取舍

牺牲时间来换取换空间

void  dome(){
    int[] array = {2, 3, 6, 1, 5, 2, 4, 9, 7, 8};
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < i; j++) {
            if (array[i] == array[j]) {
                System.out.println(i + "," + j);
                return;
            }
        }
    }
}

牺牲空间来换取换时间


void  dome2(){
    int[] array = {2, 3, 6, 1, 5, 2, 4, 9, 7, 8};
    Mapmap = new HashMap<>(16);
    for (int i = 0; i < array.length; i++) {
        if (map.get(array[i]) == null) {
            map.put(array[i],1);
        }else {
            map.put(array[i], map.get(array[i]) + 1);
        }
    }
    for (Integer key : map.keySet()) {
        if (map.get(key) == 2) {
            System.out.println(key);
            return;
        }
    }
}

下面给出一个常用排序算法的时间和空间复杂度作参考:

col 1 col 2 col 3 col 4
排序算法 时间复杂度 空间复杂度 稳定性
冒泡排序 O(n²) O(1) 稳定
选择排序 O(n²) O(1) 不稳定
直接插入排序 O(n²) O(1) 稳定
快速排序 O(nlogn) O(n²) 不稳定
堆排序 O(nlogn) O(nlogn) 不稳定
二叉树排序 O(nlogn) O(nlogn) 稳定
</section>

相关文章
|
2天前
|
弹性计算 人工智能 安全
云上十五年——「弹性计算十五周年」系列客户故事(第二期)
阿里云弹性计算十五年深耕,以第九代ECS g9i实例引领算力革新。携手海尔三翼鸟、小鹏汽车、微帧科技等企业,实现性能跃升与成本优化,赋能AI、物联网、智能驾驶等前沿场景,共绘云端增长新图景。
|
8天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
7天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
6天前
|
云安全 人工智能 自然语言处理
阿里云x硅基流动:AI安全护栏助力构建可信模型生态
阿里云AI安全护栏:大模型的“智能过滤系统”。
|
7天前
|
编解码 自然语言处理 文字识别
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
凌晨,Qwen3-VL系列再添新成员——Dense架构的Qwen3-VL-8B、Qwen3-VL-4B 模型,本地部署友好,并完整保留了Qwen3-VL的全部表现,评测指标表现优秀。
618 7
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
|
10天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
736 2