数据结构与算法-绪论

前言

    程序设计 = 数据结构+算法，如果不想当只会调API的行尸走肉，数据结构和算法就是必修课！

什么是数据结构

    数据结构就是数据元素之间存在的一种或多种关系的集合，传统上把数据结构分为物理结构和逻辑结构。

• 逻辑结构：指数据元素相互之间的关系。
• 物理结构：指数据的逻辑结构在计算机中的存储形式，实际上研究的就是如何把数据元素存储到计算机的存储器中，存储器一般指内存，硬盘之内的外部存储器一般用文件结构描述

    数据元素的存储结构形式有两种，顺序存储和链式存储。

• 顺序存储结构：把数据元素存储到地址连续的存储单元里，数据的逻辑关系和存储关系是一致的。
• 链式存储结构：把数据元素存储到任意位置的存储单元里，可以是连续的也可以不连续

什么是算法

• 算法是解决特定问题求解步骤的描述，在计算机中体现为指令的有限序列，并且每条指令表示一个或多个操作，或者是就是你泡妞的技巧和方式

     算法具有五个基本特征：

• 输入
• 输出
• 有穷性
• 确定性
• 可行性

     算法设计有要求：

• 正确性
• 可读性
• 健壮性
• 时间效率高，存储量低

    算法效率度量方法：

• 判断一个算法效率时，函数中的常量和次要项常常可以忽略，而更应该关注主项的阶数
• 输入的数据量要大

    算法时间复杂度：执行次数等于时间，用O()表示时间复杂度

• 用1取代运行时间中所有加法常数
• 运行次数函数存在最高项，只保留最高阶项
• 最高阶项存在且不是1，去除和最高阶项相乘的常数
• 最后结果就是大O阶

   常见的时间复杂度，按从小到大排序，有O（1）常数阶，O（log(2)n）对数阶，O（n）线性阶，O（nlog(2)n）nlogn阶，O（n^2）平方阶，O（n^3）立方阶，O（2^n）,O（n!）,O（n^n）

    算法空间复杂度：写代码可以用空间换时间，时间复杂度更符合算法潮流。