首页 算法学习基础-基本概念
文章
取消

算法学习基础-基本概念

一、概述

撰写时间:2019-06-07 13:35,整理时间:2023-01-18

作为一名普通的二本学校,我在很早之前就有一个目标,那就是大学之后好好找一个软件开发工作。因此学习了很多的编程基础,不过近几天面试发现,技术官总是喜欢问你算法知识。编程语言不断变化,但是很底层的知识与算法密切相关,算法也就是体现程序员内功所在。因此,从此该好好学算法。

本笔记参考马士兵老师的视频教程:https://www.bilibili.com/video/av46562560

二、基本概念

算法是数据结构与算法的简称

2.1 什么是数据结构?

Data Structure 简单的理解,数据结构就是:存储数据的不同方式 19060701.png

假如我们把5个数据比作5个鸡蛋,我们可以把它们放到一个管子里,也可以把它们放到一个框子里,这就是不同的存储方式。存储数据的不同方式就是不同的数据结构。

引申:加入我们有2,4,7,1,6,3,5个数,我们如何来存储?

  • 方式一:

我们最容易想到的方式就是把其个数挨个紧紧排在一起,中间没有任何空隙,如图所示,在计算机中我们叫做数组(实际上,)。数组的每一个存储单元大小都一样,每一个整数放到一个单元格里面。 深度截图_选择区域_20190607134827.png

  • 方式二:

我们还可以使用另外一种方式,每一个小格除了存储自己的数据以外,还存着指向下一个小格的指针(链条),这样的存储方式叫做链表。

  • 总结:

数据的存储方式有很多种,对于不同的问题我们会采取不同的存储方式,这就是我们要学的数据结构。

2.2 什么是算法(Algorithm)?

算法是同一个问题的不同解决方法。 如下面的计算题:1+2+3+……+99=?

方式一:我们使用最简单的方式就是1先加2,再加3,再加4,以此类推。 方式二:我们还可以分别计算1加99,2+98,3+97,以此类推。

同一个问题,我们有不同的解决办法,这就是算法。而算法往往是针对特定的数据结构的。

  • 假设1:对于1中的链表这种数据结构,我们如何往链表里面的7和1插入一个0?

这时候我们只需要将7和1中的链条打断,让7中的链条指向0,0中的链条指向1,这时候就构成了一个新的链条,这就完成了。

  • 假设2:对于1中的数组,我们如歌在7和1之间插入0?

那么这个算法就稍微麻烦一些了。数组之间没有空隙,我们插入不了,因此可以采取以下办法:我们重新分配一块新的空间,这是的新空间要比原来的空间要大一个单元格,也就是一个单位的数据大小。这时候先把2、4、7复制下来,再把0插进去,最后把1、6、5、3复制下去,如下图所示

深度截图_选择区域_20190607141257.png

由上面我们可以看出,对于插入算法来说,链表要比数组简单的多。当然,不能说数组就不如链表,有很多的操作数组要比链表快得多,比如说我们想访问第6个数。对于链表来说我们必须从第一个数开始,先找到第一个数,再根据第一个数顺着链条往后找,最终才能找到。二对于数组来说,找第6个数就很简单,只要知道单元格的大小,直接往后跨越6个单元格,就可以找到第6个数,所以查找对于数组来说,要比链表快。

所以,对不同的数据结构,在不同的应用场景中有不同优点和缺点,所以,选择什么样的数据结构,要根据特定的问题来决定。

总结来说,数据结构就是存储数据的不同方式,算法就是解决问题的不同方法,而算法往往是针对不同的数据结构的。

三、如何测算算法的优劣?

  • 时间测算

计算算法时间差,幅度不够循环来凑。对于一个问题,完成同样结果,我们认为所用时间越少,算法越好;

  • 空间测算

对于一个问题,如果完成同样的结果,我们认为,占用系统的空间越少,算法越好,占用系统空间越大,算法越不好。

3.1 我们如何秒速算法的优劣?Big O(欧)

O(Big O):Big O(也可以读作“大O”)用来标识复杂度。

  • 什么是时间复杂度?

计算机解决一个问题执行的时间,随着问题规模的扩大,时间的变化的规律。

  • 什么是空间复杂度?

计算机解决一个问题做占用的空间,随着问题规模的扩大,空间的变化规律。

  • 假设一

如果数组规模为10,需要找数组中的最后一个数,现在数组规模变成10万,需要找数组中的最后一个数。时间其实是一样的,这时候把时间复杂度称为O(1),O(1)表示时间复杂度是一个常数,不管数组规模扩大多少,我们需要找第几个数,所用时间是一个固定的值,此时记为O(1)。

  • 假设二

如果要访问链表中某个位置的值,这时候时间复杂度为O(n)。一般时间复杂度我们都讲的是最差的情况,在链表中,找第一个数的时间复杂度还是为O(1),而我们一般考虑的是找最后一个数的情况。所以此时复杂度为O(n)。

  • 时间复杂度一般都有什么? n2、n3、log n

  • 假设三

求一个数组的平均数?求一个数组的平均数,我们先把所有数加起来,所以一个数组规模要扩大,我们要加的数随之扩大,因此时间复杂度是O(n)。

3.2 思考:用O表示时间复杂度?

  • a.查找数组最后一个位置上的数
  • b.查找链表最后一个位置上的数
  • c.对数组求和
  • d.查找数组的最大值
本文由作者按照 CC BY 4.0 进行授权

algs.tech-考古学

Android开发中包的定义