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

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

前言

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

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

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

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

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

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

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

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

算法复杂性

时间复杂度

渐近界

以函数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


未完待续

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

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

扪心自问的问题们:

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

推荐文章

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


目录
相关文章
|
3天前
|
算法 Java
《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)
《JVM由浅入深学习【八】 2024-01-12》JVM由简入深学习提升分(JVM的垃圾回收算法)
5 0
|
4天前
|
机器学习/深度学习 人工智能 算法
技术经验解读:【转】完美洗牌算法学习
技术经验解读:【转】完美洗牌算法学习
|
12天前
|
机器学习/深度学习 算法 搜索推荐
【机器学习】Apriori算法在关联规则学习中的应用
【机器学习】Apriori算法在关联规则学习中的应用
40 0
|
12天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】Voting集成学习算法:分类任务中的新利器
【机器学习】Voting集成学习算法:分类任务中的新利器
19 0
|
14天前
|
算法 搜索推荐 JavaScript
算法学习:快速排序
算法学习:快速排序
13 1
|
14天前
|
机器学习/深度学习 存储 算法
算法学习:递归
算法学习:递归
15 0
|
14天前
|
存储 算法 Go
算法学习:数组 vs 链表
算法学习:数组 vs 链表
17 0
|
14天前
|
算法 JavaScript 前端开发
算法学习:二分查找
算法学习:二分查找
21 0
|
18天前
|
机器学习/深度学习 算法 PyTorch
【从零开始学习深度学习】43. 算法优化之Adam算法【RMSProp算法与动量法的结合】介绍及其Pytorch实现
【从零开始学习深度学习】43. 算法优化之Adam算法【RMSProp算法与动量法的结合】介绍及其Pytorch实现
|
18天前
|
机器学习/深度学习 算法 PyTorch
【从零开始学习深度学习】42. 算法优化之AdaDelta算法【基于AdaGrad算法的改进】介绍及其Pytorch实现
【从零开始学习深度学习】42. 算法优化之AdaDelta算法【基于AdaGrad算法的改进】介绍及其Pytorch实现