算法系统学习-xdm,时间复杂度到底是个啥?

简介: 该系列是基于有一定语言基础(C,C++,Java等等)和基本的数据结构基础进行的算法学习专栏,如果觉得有点吃力 😥 ,建议先了解前提知识再学习喔!本个专栏会将用更容易理解的表达去学习算法,如果在一些表述上存在问题还请各位多多指点

算法分析和评价:


在不考虑机器对算法的影响,我们对一个算法主要从时间效率和空间效率两个维度上考虑。

在算法完成功能的前提下,最好是占用的空间少而且执行时间短,事实上,两全其美的算法是不容易设计的,多数的情况是占用空间多时数据处理的步骤就少,反之占用空间少的数据处理的步骤多。

(所以经常会听到空间换时间,时间换空间的说法,包括一些语言执行上也是有这种特性,对反应的速度要求高的更多倾向于接近底层系统的繁重语言例如C,而响应速度没那么高,就选择更加简洁的语言编写)


算法的时间复杂性:


简单理解是就是执行完该算法所用的时间,一般用bigO表示,它是数量级Order的第一个字母。一个算法转换程序后所耗费的时间,主要取决与算法中执行重复执行的次数,即与语句中的频度有关(下面有详细介绍)

(这是学习算法的核心,也是无法绕开的一个问题。)


与算法执行时间相关因素:


  1. 问题中数据存储的数据结构
  2. 采用的数学模型
  3. 设计的策略
  4. 问题的规模
  5. 实现算法的设计语言
  6. 编译算法产生的机器代码的质量
  7. 计算机执行指令的速度


算法时间衡量方法:


  1. 事后分析法:指的是将算法用程序实现后,直接执行,看执行时间。缺点很明显:不同算法下时间浮动大,不够准确,工作效率低,也与我们做的算法分析的目的违背的(因此很少用,除非已经到了无可奈何的情况下)
  2. 事前分析估算法:一个特定的算法“运行工作量”的大小,只依赖与问题的规模(一般用n表示)。算法的时间效率是问题规模的函数,随着问题的规模n的增长,算法执行,时间的增长率和函数f(n)的增长相同:

网络异常,图片无法展示
|

T(n)就是我们常说的时间复杂度,O是数量级的符。


算法执行时间与原操作执行次数之和成正比


频度:其实就是该语句执行的重复的次数。例如:

for(j =1 ;j<=n;j=j+1){
  for(k=1;k<n;k=k+1){
        x=x+1;
    }
}
k=k+1 x=x+1 频度为n^2
k<n 频度为n(n+1)
j=j+1 k=1 频度为n
j=1 为1
j<=n 频度为n+1
    综上所述:时间复杂度3n^2+4n+2
复制代码


虽然上面会有一点点难以理解,但是实际上采用的是 从算法中选取一种对于说研究的问题来说是基本的原操作,以该基本操作在算法中重复执行的次数作为算法运行时间的算法的衡量准则。假设遇到下面多重层次循环结构,按照上面方法就很麻烦了

for(i=1;i<n;i++){
    for(j=1;j<n;j++){
        for(k=1;k<n;k++){
            //输出语句
    }
  }
}
时间复杂度 为 n^3 
复制代码


一般来说我们是直接忽略低阶常数项,直接保留高阶


算法的数量级


为了方便算法之间比较,算法时间复杂度均表示为:

  1. O(1) 为常数级
  2. O(logn)对数级
  3. O(n) 线性级
  4. O(c^n) 指数级
  5. O (n!) 阶乘级

时间复杂度是越来越高的,随着n的增长,通过观察曲线的变化,因此尽量不要选择指数级和阶乘级的算法。

网络异常,图片无法展示
|


算法时间复杂度的最好情况和最坏情况


有时候对于数据的输入也会影响算法,就像一些排序算法,数据的位置也会影响算法的时间复杂度,所以一般来说算法时间复杂度的衡量标准都是指 算法的平均复杂度。

目录
相关文章
|
8天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1天前
|
机器学习/深度学习 算法 5G
基于MIMO系统的SDR-AltMin混合预编码算法matlab性能仿真
基于MIMO系统的SDR-AltMin混合预编码算法通过结合半定松弛和交替最小化技术,优化大规模MIMO系统的预编码矩阵,提高信号质量。Matlab 2022a仿真结果显示,该算法能有效提升系统性能并降低计算复杂度。核心程序包括预编码和接收矩阵的设计,以及不同信噪比下的性能评估。
10 3
|
5天前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
8天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
8天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
8天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
8天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
8天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
15天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
1天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。