loader image

算法基本概念

408
6
数据结构
5
数据结构到底在学什么？（开篇）
数据结构绪论
算法基本概念
数据结构--时间复杂度
数据结构--空间复杂度
计算机组成原理
0
操作系统
0
计算机网络
0
408简介

什么是算法？

程序 = 数据结构 + 算法

数据结构

我们天天不是写程序就是在写程序的路上，那么你知道程序是由什么组成的吗？

答案就是由数据结构和算法组成的。然而我们在之前的几篇文章中已经讲解了数据结构就是：将现实世界的问题信息化，并且将信息存进计算机。同时还要实现对数据结构的基本操作。

就比如我们在前几篇文章中使用到的例子就是海底捞的排队系统：

  • 该系统的数据结构是使用队列。
  • 并且实现一些跟队列相关的基本操作
    1. 队头元素出队
    2. 新元素入队
    3. 输出队列长度
    4. 交换第 i 号和第 j 号的位置
    5. ...

在这里我们使用这个队列去表示海底捞的排队系统，其实就是把现实世界的问题信息化了。

算法

而算法就是如何处理这些信息，以解决实际问题。

比如现在有一个现实的问题：带小孩的顾客优先就餐，接下来我们就来设计一个算法：

  • 执行基本操作2.（新顾客取号）
  • 一次对比前面桌的信息，如果前面卓没有带小孩，就执行操作4.（调换带小孩的这桌新顾客至另一桌带小孩的后面一桌）

算法的五个特性

有穷性

一个算法必须总在执行有穷步之后结束，且每一步都可在又穷时间内完成。

注意：

算法必须是有穷的：

我们认为如果算法是无穷的就是没办法解决该问题。没办法解决该问题该算法就不能称之为算法，因为算法是解决问题的，解决不了问题就不能算作算法。（可能有点绕）

我举一个数学例子你们就懂了。找一个数n要大于5，现在我们找到了一个n是小于5的，那么这个n一定不大于5就应该是成立的。3 < 5 立即推 3 ≯ (不大于) 5

而程序可以是无穷的：

一个程序可以永无止尽的运行下去，算法是集成在程序中的，算法是用来解决问题的，所以算法是必须有穷的。程序相当于是一个环境，这个环境可以永久存在。

确定性

算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。

如果相同的输入，最后得出的结果不是唯一的，那么这就不能称之为算法。

可行性

算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。

输入

一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。

丢给算法处理的数据。

输出

一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。

算法处理完丢给我们的数据。

“好”算法的特质

正确性

算法应能够正确地解决求解问题。

可读性

算法应具有良好的可读性，以帮助人们理解。

如果说你的算法不具有可读性，那就不是一个好的算法。

image-20220618002051994

注意：

算法可以用伪代码描述，甚至可以用文字描述。最重要的一点是”无歧义“地描述出解决问题的步骤

健壮性

输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。

高效率（数据结构中重点研究）

执行速度快（时间复杂低）

低存储量需求（数据结构中重点研究）

不费内存（空间复杂度低）

结束语

数据结构中我们着重研究的就是查找和排序。

本人菜鸟一枚，仅分享学习笔记和经验。若有错误欢迎指出！共同学习、共同进步 🙂

6人评论了“算法基本概念”

发表评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注

Scroll to Top