一个好的算法应该如何测评

作者: _涼城 | 来源:发表于2020-03-31 21:39 被阅读0次

数据结构是计算机存储、组织数据的方式。研究的是数据的逻辑结构与数据的物理结构以及它们之间的相互关系，精心选择的数据结构可以带来更高的运行或存储效率。在数据结构这门学科中有一些基本术语，如：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、物理结构、数据类型等。

数据与结构

数据

数据对象是相互之间存在一种或者多种特定关系的数据元素的集合，而数据元素则是由若干个数据项组成的，数据元素是组成数据对象的基本单位。

结构

数据元素之间不是独立的，存在特定的关系，这些关系就是结构。

//声明一个 数据 结构体
struct Data1
{
   char element1; //数据项1
                   //  .
                   //  .
                   //  .
   char elementn; //数据项n
};

int main(int argc, char const *argv[])
{
   
    struct Data1 d1; // 数据元素
    struct Data1 dArry[10]; //数据对象

    Data1.element1 = '1'; //数据项
    Data1.elementn = 'n'; //数据项

   return 0;
}

逻辑结构与物理结构
- 逻辑结构
  
  逻辑结构是反应数据元素之间的逻辑关系的数据结构，逻辑关系是指数据元素之间的前后间关系。
  
  包括:
  1. 集合（数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系）
  2. 线性结构（数据结构中的元素存在一对一的相互关系） eg. 队列、栈、线性表、串
  3. 树形结构（数据结构中的元素存在一对多的相互关系） eg. 树、堆
  4. 图形结构（数据结构中的元素存在多对多的相互关系）

物理结构

物理结构是指数据的逻辑结构在计算机存储空间的存放形式，计算机内表示可以分为顺序存储和非顺序存储，常用的有
1. 顺序存储结构
  
  在存储器中连续开辟一段空间，元素在存储器中的相对位置来表示数据元素之间的逻辑关系
2. 链式存储结构
  
  借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

算法

数据结构就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。

算法研究的目的是为了更有效的处理数据，提高数据运算效率。数据的运算是定义在数据的逻辑结构上，但运算的具体实现要在存储结构上进行。

算法的特征
1. 输入项
2. 输出项
3. 有穷性
4. 确定性
5. 可行性

算法设计的要求
1. 正确性
2. 可读性
3. 健壮性
4. 时间复杂度
5. 空间复杂度
时间复杂度

算法执行所需的工作量，常用大O符号表述
空间复杂度

算法在运行过程中临时占用存储空间大小的量度，常用大O符号表述
大O表示法
- 用常数1取代运行时间所有常数 $O(1)$
- 在修改运行次数函数中只保留最高阶项, eg. $n^3 + 2n^2 + 5$ -> $O(n^2)$ ，当 n 增大时， $n^2$ ;项将开始占主导地位，而其他各项可以被忽略
- 如果在最高阶存在且不等于1，则去除这个阶项相乘的常数 $2n^3$ -> $O(n^3)$
- 常用的函数阶
  
  符号名称
  
  O(1) 常数（阶，下同）
  
  O( $log n$ ) 对数
  
  O(n) 线性
  
  O( $n log n$ ) 线性对数
  
  O( $n^2$ ) 平方
  
  $O(n^3)$ 立方
  
  O( $c^n$ ) 指数阶
  
  O(n!) 阶乘
  
  $O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)$