数据结构基本概念与算法和算法分析|Bobby Blog

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

在计算机科学中，“数据结构”不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。

数据：对客观事物的符号表示，所有能输入到计算机中并被计算机程序所处理的符号的总称。数据是计算机程序加工的原料。

讨论一种数据结构时，我们通常要关注三个方面：逻辑结构、物理结构（存储结构）、数据的运算。

数据元素之间的逻辑关系。通常有4类基本结构：

数据及其逻辑结构在计算机中的表示。实质上是内存分配，以确定元素及元素之间的关系的表示。一般有两种：

施加在数据上的运算包括运算的定义和实现。定义是针对逻辑结构的，指出运算的功能；实现是针对存储结构的，指出具体的操作步骤。

数据的逻辑结构属于用户视图，是面向问题的，反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是面向计算机的。

一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是不同的。

抽象数据型（abstract data type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。

ADT的形式化定义是三元组：ADT=(D,S,P)，其中D是数据对象，S是D上的关系集，P是对D的基本操作。

ADT是程序设计语言中数据类型概念的进一步推广和进一步抽象。

度量一个程序的执行时间和空间通常有两种方法，事后统计和事前分析。

事后统计：将算法实现，测算其时间和空间开销。优点是：准确的实测值。缺点是：编写实现将花费较多的时间和精力；所得实验结果依赖于计算机的软硬件等环境因素。
事前分析：对算法所耗资源的一种估算方法。撇开与计算机硬件、软件有关的因素，认为一个特定算法“运行工作量”大大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作 T(n) = O(f(n))，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的正常率相同，称做算法的渐进时间复杂度，简称时间复杂度。

大O符号的定义为：若存在两个正的常数c和n₀，对于任意n≥n₀，都有T(n)≤c*f(n)，则称T(n)=O(f(n))。如下图：
大O符号.png

在计算算法时间复杂度时，可以忽略所有的低次幂（低阶）项和最高次幂（最高阶）项的系数，例如若

A(n) = a_mn^m + a_m-1n^m-1 + ... + a₁n + a₀ 是一个m次多项式，则A(n) = O(n^m)。

例如下面的程序，问题规模是n，基本语句是sum2++，复杂度是O(n²)

        for (int i = 0; i < n; i++) {
            sum1++;
            for (int j = 0; j < n; j++) {
                sum2++;
            }
        }

设T₁(n) = O(f(n))，T₂(n) = O(g(n))，则

首先求出程序中各语句、各模块的运行时间，在求整个程序的运行时间。各语句、各模块分析应遵循的规则如下：

赋值语句或读/写语句：运行时间通常取O(1)，有函数调用的除外，此时要考虑函数的执行时间。
语句序列：运行时间由加法法则确定，既该序列中耗时最多的语句运行时间。
分支语句：运行时间由条件测试（通常为O(1)）加上分支中运行时间最长的语句运行时间。
循环语句：一个循环的运行时间，是内部语句运行时间乘以迭代次数；嵌套循环需要从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。
递归调用：对于递归调用，我们可以画出其递归树，找出规律，令每个递归函数对应于一个未知的时间开销函数T(n)，其中n是该函数参数的大小，之后列出关于T的递归方程并求解。