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

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

前言

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

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

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

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

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

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

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

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

算法复杂性

时间复杂度

渐近界

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


未完待续

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

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

扪心自问的问题们:

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

推荐文章

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


目录
相关文章
|
12天前
|
算法 JavaScript 前端开发
第一个算法项目 | JS实现并查集迷宫算法Demo学习
本文是关于使用JavaScript实现并查集迷宫算法的中国象棋demo的学习记录,包括项目运行方法、知识点梳理、代码赏析以及相关CSS样式表文件的介绍。
第一个算法项目 | JS实现并查集迷宫算法Demo学习
|
16天前
|
XML JavaScript 前端开发
学习react基础(1)_虚拟dom、diff算法、函数和class创建组件
本文介绍了React的核心概念,包括虚拟DOM、Diff算法以及如何通过函数和类创建React组件。
16 2
|
18天前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿!Python 算法设计与分析实战,教你如何精准评估与优化!
在 Python 编程中,算法的性能至关重要。本文将带您深入了解算法复杂度的概念,包括时间复杂度和空间复杂度。通过具体的例子,如冒泡排序算法 (`O(n^2)` 时间复杂度,`O(1)` 空间复杂度),我们将展示如何评估算法的性能。同时,我们还会介绍如何优化算法,例如使用 Python 的内置函数 `max` 来提高查找最大值的效率,或利用哈希表将查找时间从 `O(n)` 降至 `O(1)`。此外,还将介绍使用 `timeit` 模块等工具来评估算法性能的方法。通过不断实践,您将能更高效地优化 Python 程序。
32 4
|
16天前
|
算法 程序员 Python
程序员必看!Python复杂度分析全攻略,让你的算法设计既快又省内存!
在编程领域,Python以简洁的语法和强大的库支持成为众多程序员的首选语言。然而,性能优化仍是挑战。本文将带你深入了解Python算法的复杂度分析,从时间与空间复杂度入手,分享四大最佳实践:选择合适算法、优化实现、利用Python特性减少空间消耗及定期评估调整,助你写出高效且节省内存的代码,轻松应对各种编程挑战。
25 1
|
2月前
|
算法
【初阶数据结构】复杂度算法题篇
该方法基于如下的事实:当我们将数组的元素向右移动 k 次后,尾部 kmodn 个元素会移动至数组头部,其余元素向后移动 kmodn 个位置。
20 1
|
2月前
|
机器学习/深度学习 人工智能 资源调度
【博士每天一篇文献-算法】连续学习算法之HAT: Overcoming catastrophic forgetting with hard attention to the task
本文介绍了一种名为Hard Attention to the Task (HAT)的连续学习算法,通过学习几乎二值的注意力向量来克服灾难性遗忘问题,同时不影响当前任务的学习,并通过实验验证了其在减少遗忘方面的有效性。
54 12
|
2月前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
|
2月前
|
算法 NoSQL 中间件
go语言后端开发学习(六) ——基于雪花算法生成用户ID
本文介绍了分布式ID生成中的Snowflake(雪花)算法。为解决用户ID安全性与唯一性问题,Snowflake算法生成的ID具备全局唯一性、递增性、高可用性和高性能性等特点。64位ID由符号位(固定为0)、41位时间戳、10位标识位(含数据中心与机器ID)及12位序列号组成。面对ID重复风险,可通过预分配、动态或统一分配标识位解决。Go语言实现示例展示了如何使用第三方包`sonyflake`生成ID,确保不同节点产生的ID始终唯一。
go语言后端开发学习(六) ——基于雪花算法生成用户ID
|
2月前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-算法】连续学习算法之HNet:Continual learning with hypernetworks
本文提出了一种基于任务条件超网络(Hypernetworks)的持续学习模型,通过超网络生成目标网络权重并结合正则化技术减少灾难性遗忘,实现有效的任务顺序学习与长期记忆保持。
35 4
|
2月前
|
存储 机器学习/深度学习 算法
【博士每天一篇文献-算法】连续学习算法之RWalk:Riemannian Walk for Incremental Learning Understanding
RWalk算法是一种增量学习框架,通过结合EWC++和修改版的Path Integral算法,并采用不同的采样策略存储先前任务的代表性子集,以量化和平衡遗忘和固执,实现在学习新任务的同时保留旧任务的知识。
76 3