舒先生

概述

Mr.Shu2022年10月22日
  • 算法
  • 入门
  • 概述
大约 3 分钟

概述

算法与数据结构作为计算机四大件之一，是一门非常重要的知识。

程序=算法+数据结构。

注意 后续我会将算法与数据结构简称为 DS

图片

数据结构基本概念

数据结构是一种存储和组织数据的方式，以便于访问和修改。数据结构包括数据的逻辑结构、数据的储存结构以及数据的运算,即按照某种逻辑关系组织起来的一批数据，按一定的映射方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算几何。

  • 数据的逻辑结构：反应数据元素之间的关系。有集合、线性结构、树形结构、图形结构。
  • 数据的存储结构：逻辑结构在计算机的存储现象，是逻辑结构在计算机中的实现，他包括数据元素的表示和元素之间关系的表示。有顺序存储结构（数组），链式存储结构（链表），索引存储结构、离散存储结构等。
  • 数据的运算：对数据施加的操作，通过算法描述。

算法的基本概念

计算机求解一个问题所需的一系列步骤。

算法特性

  1. 输入：一个算法有 0 个或者多个输入、以刻画运算对象的初始情况、所谓 0 个输入是指算法本身给出了条件。
  2. 输入： 一个算法有一个或者对个输出，以反映对输入数据加工后的结果，没有输出的算法是毫无意义的。
  3. 有穷性：算法必须能在执行有限个步骤之后终止。
  4. 确切性：算法的每一步骤必须有确切的定义。
  5. 可行性：算法执行的任何计算都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成。

设计要求

  1. 正确性： 设计的算法能满足具体时间问题的需求，并且任何合法的输入都会得出正确的输出。
  2. 可读性： 是指算法被写好后，该算法理解的难易程度，一个算法可读性的好坏十分重要，如果一个算法比较抽象且难以理解，那么这个算法就不利于交流和推广使用，对于修改、扩展、维护来说十分不方便，因此，在追求高效的同时，也应是算法尽量简明易懂。
  3. 健壮性：当输入数据非法时，算法也会做出相应的判断，而不会因为输入的错误而造成的瘫痪。
  4. 时间效率高（时间复杂度）和需要的存储空间少 (空间复杂度) 。

时间复杂度

用大 O 表示

  1. 用常数 1 来取代运行时间中所有的加法常数。
  2. 在修改后的运行次数函数中，只保留最高项。
  3. 如果最高项目存在不是 1，则去除与这个项相乘的常数。

简单练习 1

在你的通讯录中找到你要找的人,假设通讯录中有 N 个人。

两种方式，简单查找和二分查找。 简单查找: 一个一个查找，需要查找 N 次。 二分查找: 按照姓名的字母排序，首先查找.

DS 书籍以及课程推荐

Loading...