第2章 算法分析基础

2-1 算法的时间复杂度分析

2.1.1 输入规模与基本语句

  • 输入规模:算法处理数据的规模,通常用 n 表示。

  • 基本语句:执行次数与输入规模直接相关的关键操作。

  • 例2.1 顺序查找

    int SeqSearch(int A[], int n, int k) {  for (int i = 0; i < n; i++)  if (A[i] == k) break;  if (i == n) return 0;  else return (i + 1);  
    }
    
    • 输入规模 n;基本语句是“比较 A[i] == k”

2.1.2 渐近分析

  • 大 O、大 Ω、大 Θ

    • T(n)=O(f(n)):∃ c, n₀, ∀ n ≥ n₀, T(n) ≤ c·f(n)

    • T(n)=Ω(f(n)):∃ c, n₀, ∀ n ≥ n₀, T(n) ≥ c·f(n)

    • T(n)=Θ(f(n)):同时满足 O(f(n)) 和 Ω(f(n))

  • 例:若 T(n) ≤ 100n + n 则 T(n)=O(n)

    • 取 n₀=5, c=101, 则 ∀ n ≥ 5, T(n) ≤ 101n → O(n)

  • 常见增长阶
    1 < log n < n < n log n < n² < n³ < … < 2ⁿ < n!

  • 例2.4 合并算法

    void Union(int A[], int n, int B[], int m, int C[]) {int i=0, j=0, k=0;while (i<n && j<m) {if (A[i] <= B[j]) C[k++] = A[i++];else C[k++] = B[j++];}while (i<n) C[k++] = A[i++];while (j<m) C[k++] = B[j++];
    }
    
    • 时间复杂度 O(n + m)

2.1.3 最好、最坏和平均情况

  • 当算法执行代价依赖于不同输入时,需要分别分析:

    • 最好情况:最少操作次数;

    • 最坏情况:最多操作次数;

    • 平均情况:所有输入实例上的平均操作次数。

  • 顺序查找例

    • 最好:第1个元素即中,比较1次;

    • 最坏:未找到或在末尾,比较n次;

    • 平均:约(n + 1)/2次


2-2 算法的空间复杂度分析

  • 空间复杂度 = 输入/输出数据占用 + 算法本身占用 + 辅助空间

    1. 输入/输出数据:题目本身的数据结构;

    2. 算法本身:局部变量、常量,通常为 O(1);

    3. 辅助空间:临时数组、递归栈等。

  • 示例

    • CommonFactor 求最大公约数:仅用常数级局部变量,O(1);

    • BubbleSort:只用固定数量的索引和临时变量,O(1);

    • Merge:需要长度为 n 的临时数组,O(n)。


2-3 算法的实验分析

  • 实验分析:将算法实现为程序,上机运行,实际测算时空开销

  • 常用度量方法

    1. 计数法:插入计数器,记录关键语句执行次数;

    2. 计时法:记录程序段开始和结束时间,计算时间差。

  • 例 BubbleSort 实验

    void BubbleSort(int r[], int n) {int j, temp, count1=0, count2=0, bound, exchange=n-1;while (exchange != 0) {bound = exchange; exchange = 0;for (j = 0; j < bound; j++)if (++count1 && r[j] > r[j+1]) {temp = r[j]; r[j] = r[j+1]; r[j+1] = temp;count2 += 3; exchange = j;}}cout<<"比较次数="<<count1<<",移动次数="<<count2<<endl;
    }
    
    • 目的:统计比较次数和移动次数

  • Collatz 过程实验

    • 规则:n 为奇数 → 3n+1,否则 → n/2,直到 n=1;

    • 例 n=9:{9,28,14,…,1};

    • 例 n=27:77步到9232,再32步到1。


2-4 拓展与演练:最优算法与下界

  • 下界 Ω 表示法
    若 ∃ c, n₀, ∀ n ≥ n₀, T(n) ≥ c·g(n),则 T(n)=Ω(g(n)),g(n) 是问题的时间下界

  • 最优算法
    如果问题已知下界 g(n),且算法满足 T(n)=Θ(g(n)),则该算法为最优。

  • 例2.10 最小值算法

    int ArrayMin(int a[], int n) {int min = a[0];for (int i = 1; i < n; i++)if (a[i] < min) min = a[i];return min;
    }
    
    • 比较次数下界 Ω(n),算法时间 O(n),故为最优。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/223.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

4.系统定时器基本定时器

目录 系统定时器 系统定时器&#xff08;systick&#xff09;--内核 系统定时器结构 系统滴答定时器寄存器--内核 定时周期的确定公式 配置滴答定时器 系统定时器应用 应用1.定时器构造时间点任务&#xff0c;解决while循环阻塞问题 应用2.定时器构造精准的ms延时 应…

基于SpringBoot和PostGIS的应急运输事件影响分析-以1.31侧翻事故为例

目录 前言 一、技术实现路径 1、需要使用的数据 2、空间分析方法 二、相关模块设计与实现 1、运输路线重现开发 2、事故点影响范围实现 3、WebGIS可视化实现 三、讨论 1、界面结果展示 2、影响范围分析 四、总结 前言 在交通运输发达的当今社会&#xff0c;应急运输…

Python爬虫(20)Python爬虫数据存储技巧:二进制格式(Pickle/Parquet)性能优化实战

目录 背景介绍一、二进制存储的核心优势二、Python Pickle&#xff1a;轻量级对象序列化1. 基本介绍2. 代码示例3. 性能与局限性 三、Apache Parquet&#xff1a;列式存储的工业级方案1. 基本介绍2. 代码示例&#xff08;使用PyArrow库&#xff09;3. 核心优势 四、性能对比与选…

C++从入门到实战(十三)C++函数模板与类模板初阶讲解

C从入门到实战&#xff08;十三&#xff09;C函数模板与类模板初阶讲解 前言一、为什么需要模板1. 函数重载的问题2. 泛型编程和模板的作用 二、函数模板2.1 函数模板格式2.2 函数模板的原理2.3 函数模板的实例化&#xff08;1&#xff09;隐式实例化&#xff1a;&#xff08;2…

游戏引擎学习第261天:切换到静态帧数组

game_debug.cpp: 将ProfileGraph的尺寸初始化为相对较大的值 今天的讨论主要围绕性能分析器&#xff08;Profiler&#xff09;以及如何改进它的可用性展开。当前性能分析器已经能够正常工作&#xff0c;但我们希望通过一些改进&#xff0c;使其更易于使用&#xff0c;特别是在…

《Python星球日记》 第36天:线性代数基础

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏:《Python星球日记》,限时特价订阅中ing 目录 一、标量、向量、矩阵的基本概念1. 标量2. 向量3. 矩阵二、矩阵运算1. 矩阵加法2. 矩阵乘法3. 矩…

【SF顺丰】顺丰开放平台API对接(注册、API测试篇)

1.注册开发者账号 注册地址&#xff1a;顺丰企业账户中心 2.登录开发平台 登录地址&#xff1a;顺丰开放平台 3.开发者对接 点击开发者对接 4.创建开发对接应用 开发者应用中“新建应用”创建应用&#xff0c;最多创建应用限制数量5个 注意&#xff1a;需要先复制保存生产校验…

【Linux】进程地址空间

&#x1f4dd;前言&#xff1a; 这篇文章我们来讲讲进程地址空间&#xff1a; &#x1f3ac;个人简介&#xff1a;努力学习ing &#x1f4cb;个人专栏&#xff1a;Linux &#x1f380;CSDN主页 愚润求学 &#x1f304;其他专栏&#xff1a;C学习笔记&#xff0c;C语言入门基础…

【Java学习】反射

目录 反射类 一、泛型参数 二、反射类类型 三、实例化 1.实例化材料 2.结构信息可使用化 四、使用 1.Class —类完整结构信息 1.1Class<类>实例化 1.2Class<类>实例获取 1.2.1Class类静态获取&#xff1a; 1.2.2信息类静态获取 1.2.3信息类非静态获取 …

MVC、MVP、MVVM三大架构区别

1、MVC架构 M&#xff08;Model&#xff09;&#xff1a;主要处理数据的存储、获取、解析。 V&#xff08;View&#xff09;&#xff1a;即Fragement、Activity、View等XML文件 C&#xff08;Controller&#xff09;&#xff1a;主要功能为控制View层数据的显示&#xff0c;…

科创大赛——知识点复习【c++】——第一篇

目录 输入 一、cin 二、scanf 三、gets 四、getchar 五、fgets 输出 一、cout 二、printf 基本数据类型 一&#xff0c;数据类型有哪些&#xff1f; 二&#xff0c;整型&#xff08;Integer Types&#xff09; 1&#xff0c;修饰符 2&#xff0c;整型数据的数据范…

java学习之数据结构:四、树(代码补充)

这部分主要是用代码实现有序二叉树、树遍历、删除节点 目录 1.构建有序二叉树 1.1原理 1.2插入实现 2.广度优先遍历--队列实现 3.深度优先遍历--递归实现 3.1先序遍历 3.2中序遍历 3.3后序遍历 4.删除 4.1删除叶子节点 4.2删除有一棵子树的节点 4.3删除有两棵子树的节…