算法学习 | 加深了解算法的复杂度

简介: 本篇从时间复杂度和空间复杂度出发,深入了解一下算法的复杂性。

前言

开篇,先来看看我的技术学习良性循环图,将对技术的热情提起来。

前面一篇对算法有了初步的了解和认知。

算法最吸引我的有三个点:

  • 在算法中,存在秩序和规则,工作中我喜欢有条不紊;
  • 算法可以帮助我解决一些问题;
  • 探索解题过程很有趣,虽然过程会有点曲折。

前一篇提到了,「好」算法,高效性和低存储性是两个标准,这两个标准应对的是算法的运行时间和存储空间。

算法的运行时间一般称之为时间复杂度。

算法的存储空间的大小一般称之为空间复杂度。

本篇从这两点出发,深入了解一下算法的复杂性。

算法复杂性

时间复杂度

渐近界

以函数f(n)为例,O(f(n))表示时间复杂度渐进上界,Ω(f(n))时间复杂度渐进下界。

渐进上界代表算法完成工作所需的最长的时间。

渐进下界代表算法完成工作所需的最佳的时间(最短时间)。

这两个值可以用来衡量算法的时间复杂度。通常用O(f(n))表示时间复杂度。

来看一个计算的例子

functionfunC(n) {
leti=1; // 运行1次while (i<n) {
// 可假设运行x次i=i*2; // 可假设运行x次  }
}

假设可运行x次,当i=n时结束,由此可以得到公式:

则可以求得x的值为:

时间复杂度渐近上界为:

O(f(n))=O()

渐近准确界

θ(f(n))表示渐近准确界,θ会更加精确。当即接近渐近上界又接近渐近下界时就是渐近准确界。

三个边界的图形实例

空间复杂度

算法储存空间分类

算法占用的储存空间包括:

  • 算法本身:可以忽略不计(应该吧,我看大部分文章中,列等式的时候没有它)
  • 输入空间:输入数据所占的空间
  • 输出空间:算法运行之后,存储输出数据所需的空间大小
  • 辅助空间:算法执行中使用的额外空间或临时空间

当输入数据大小为N时,空间复杂度 = 辅助空间+输出空间。其中辅助空间是衡量算法空间复杂度的关键因素。

常数O(1)

算法执行中的辅助空间大小固定,不随输入数据N的大小而变化,此时算法的空间复杂度为常量,空间复杂度用O(1)表示。

let a = 1;

let b = a;

a+=1;

线性O(N)

当算法分配的空间是N 呈线性关系的任意类型的集合(如数组等)时,空间复杂度用 O(n)表示

letarr=newArray(n); // 数组占用的大小为n


未完待续

以前对算法的时间复杂度和空间复杂度,只是知道皮毛。认真学习之后,有了更深入的了解。

上篇文章中有五个问题,只回答了前两个,后面三个还在思考中,对于「如何实现从掌握到精通?」这个问题,已经有点眉目了,我整理整理,下篇详细聊聊。

扪心自问的问题们:

  • 学到的算法是否可以应用到工作中?
  • 学到的算法怎么应用到工作中?
  • 如何实现从掌握到精通?

推荐文章

在学习的过程中,查找了一些资料,其中有些写的比较好的文章,我列出来推荐给大家


目录
相关文章
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
13天前
|
机器学习/深度学习 人工智能 自然语言处理
【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
阿里云人工智能平台 PAI 与复旦大学王鹏教授团队合作,在自然语言处理顶级会议 EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
17天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
17天前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】
|
17天前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
IKU达人之数据结构与算法系列学习×单双链表精题详解、数据结构、C++、排序算法、java 、动态规划 你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!