---
title: 算法学习基础-基本概念
date: 2023-01-18 13:21:00
categories: [数据结构与算法]
tags: []
pin: false
---

## 一、概述

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

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

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

## 二、基本概念

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

### 2.1 什么是数据结构？

Data Structure
简单的理解，数据结构就是：存储数据的不同方式
![19060701.png](/img/algorithm/01-01.png)

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

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

- 方式一：

我们最容易想到的方式就是把其个数挨个紧紧排在一起，中间没有任何空隙，如图所示，在计算机中我们叫做数组（实际上，）。数组的每一个存储单元大小都一样，每一个整数放到一个单元格里面。
![深度截图_选择区域_20190607134827.png](/img/algorithm/01-02.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](/img/algorithm/01-03.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.查找数组的最大值