大话数据机构_算法 | 万能的小江

学习 C/C++ 数据结构算法

学习数据结构 C/C++

发布日期: 2021-04-10

作者: InImpasse

文章字数: 3.6k

阅读时长: 13 分

阅读次数:

欢迎关注我的微信公众号【万能的小江江】

抽象数据类型ADT(Abstract Data Type)：指一个数学模型及定义在该模型上的一组操作

结构

逻辑结构

集合结构
线性结构
树形结构
图形结构

物理结构

顺序存储结构
链接存储结构

tips：如果你中途放弃了，之前所有的努力和付出都会变得没有价值

算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作

数据结构与算法的关系

在学习数据结构的过程中，算法是为了帮助更好地理解数据结构

两种算法的比较

现在我们要写出计算从1加到100结果的程序，正常可能会这样写：

int i,sum = 0,n = 100;
for(i = 1 ;i <= n;i++)
{
    sum = sum + 1;
}
printf("%d",sum);

用高斯的方法：

int i,sum = 0,n = 100;//数据比较大的话需要更改整型变量为长整型，否则会溢出
sum=(1 + n) *  n/2;
print("%d",sum);

算法的定义

算法（Alogorithm）在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作

这里提到的指令，能被人或机器等计算装置执行，可以是计算机中的指令，也可以是我们平时的语言和文字

为了解决某个或某类问题，需要把指令表示成一定的操作序列，操作序列包括一组操作，，每一个操作都完成特定的功能，就是算法

算法的特性

算法的五个基本特征：输入、输出、有穷性、可行性

输入、输出

算法具有零个或多个输入，但是一定需要输出，输出的形式可以是打印输出，也可以是返回一个或多个值

有穷性

指算法在执行完有限的步骤后，自动结束，不会出现无限循环，且每个步骤在可接受的时间内完成

确定性

算法的每一个步骤都有确定的含义，不会出现二义性，每个步骤被精确定义而无歧义

可行性

算法的每一步必须都是可行的，每一步都能通过执行有限次数完成

算法设计的要求

正确性

算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案

正确性层次

算法程序没有语法错误
算法程序对于合法的输入数据能够产生满足要求的输出结果
算法程序对于非法的输入数据能够得到满足规格说明的结果（正常情况下，以此为正确性标准）
算法程序对于精心选择的，甚至刁难的测试数据都有满足要求的输出结果

可读性

写代码的目的，一方面是为了让计算机执行，还有就是为了便于他人阅读，让人理解和交流，也为自己之后阅读代码提供便利

可读性是算法和实现它的代码好坏很重要的标志

健壮性

当输入数据不合法时，算法也能做出相关的处理，而不是产生异常或莫名其妙的结果

时间效率高和存储量低

尽量用最短的时间，最少的资源，办最大的事

算法效率的度量方法

事后统计方法

通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序运行时间进行比较，从而确定算法效率的高低

缺陷

必须依照算法事先编好程序，需要花费大量时间和精力
时间的比较容易受到计算机硬件和软件等环境因素的影响，不同的电脑不一样
算法的测试数据设计困难，程序的运行时间与测试数据的规模有很大关系，效率高的算法在小的测试数据面前往往得不到什么体现

事前分析估算法

在计算机程序编制前，依据统计方法对算法进行估算

正常情况下影响运行消耗时间的因素

算法的策略、方法
编译产生的代码质量（需要软件的支持）
问题的输入规模
机器执行指令的速度（看硬件性能）

所以正常情况下，主要是取决于算法的好坏和问题的输入规模

举例

第一种算法：

int i,sum = 0,n = 100;//执行1次
for(i = 1;i < n;i++)//执行n+1次
{
    sum = sum + 1;//执行n次
}
printf("%d",sum);//执行1次

总计执行2n+3次

第二种算法：

int i,sum = 0,n = 100;//执行1次
sum=(1 + n) * n/2;//执行1次
print("%d",sum);//执行1次

总计执行3次

延展：

int i,j,x = 0,sum = 0,n = 100;//执行1次
for(i = 1;i <= n;i++)
{
    for(j = 1;j <= n;j++)
    {
        x++;                //执行n x n次
        sum = sum + x;
    }
}
printf("%d",sum);            //执行1次

总计执行n²+2次

由此可看出，虽然三种算法结果一样，但是耗费的时间差很多，在分析程序运行时间时，最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤

函数的渐近增长

给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有n>N,f(n)总是比g(n)大，那么我们说f(n)的增长渐近快于g(n)

判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，应该更关注主项的阶次

某个算法，随着n的增大，它会越来越优于另一算法，或者越来越差于另一算法

算法的时间复杂度

算法时间复杂度定义

时间复杂度就是一个程序需要执行的次数多少？

推到大O阶方法

用常数1取代运行时间中的所有加法常数
在修改后的运行次数函数中，只保留最高阶项
如果最高阶项存在且不是1，则去除与这个项相乘的常数，得到的结果就是大O阶

常数阶

int i,sum = 0,n = 100;//执行1次
sum=(1 + n) * n/2;//执行1次
print("%d",sum);//执行1次

为什么时间复杂度是O(3)，不是O(1)?

这个算法的运行此时函数f(n)=3，根据我推导大O阶的方法，第一步是把常数项3改为1。之后在保留最高次项的时候发现，它没有最高次项，所以这个算法的时间复杂度是O(1)

int i,sum = 0,n = 100;//执行1次
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;
sum=(1 + n) * n/2;//共执行10次
print("%d",sum);//执行1次

如这个代码，无关n是多少，两段代码就是3次和12次执行次数的差异。执行时间恒定的算法，我们称之为具有O(1)的时间复杂度，又叫常数阶

不管常数是多少，我们都记作O(1)，不能是其他数字

对于分支结构，无论是真或假，执行的次数都是恒定的，不会随着n的变大而发生变化， 所以单纯的分支结构（不包含在循环结构中），时间复杂度也是O(1)

线性阶

要确定某个算法的阶次，我们常常需要确定某个特定语句或者某个语句集运行的次数。因此，如果要分析算法的复杂度，关键就是要分析循环结构的运行情况

int i;
for(i = 0; i < n;i++)
{
    //时间复杂度为O(1)的程序步骤序列
}
    //时间复杂度为O(n)

对数阶

int count = 1;
while(count < n)
{
    count = count * 2;
    //时间复杂度为O(1)的程序步骤序列
}

每次count乘以2之后，就距离n更近了一分。有多少个2相乘后大于n，就会退出循环。由2的x次方=n，得到x=log2n，所以这个循环的时间复杂度为O(logn)

平方阶

int i,j;
for(i = 0;i < n;i++)
{
    for(j = 0;j < n;j++)
    {
    //时间复杂度为O(1)的程序步骤序列
    }
}

对外层的循环，不过是内部这个时间复杂度为O(n)的语句，再循环n次，所以这段代码的时间复杂度为O(n²)

如果外循环次数改为m，时间复杂度就变为O(m*n)

int i,j;
for(i = 0;i < m;i++)
{
    for(j = 0;j < n;j++)
    {
    //时间复杂度为O(1)的程序步骤序列
    }
}

循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数

int i,j;
for(i = 0;i < n;i++)
{
    for(j = i;j < n;j++)//注意是j=i
    {
    //时间复杂度为O(1)的程序步骤序列
    }
}

i=0，内循环执行了n次；i=n-1，内循环执行了n-1次…当i=n-1时，执行了1次，内循环总的执行次数为：

n+(n-1)+(n-2)+...+1=n(n+1)/2=n²/2+n/2

步骤1：没有加法常数，不予考虑

步骤2：只保留最高阶项，只保留n²/2

步骤3：去除这个项相乘的常数，所以时间复杂度是O(n²)

例子1

int i,j;
for(i = 0;i < n;i++)
{
    function(i);
}
void function(int count)
{
    printf(count);
}

function函数的时间复杂度是O(1)，所以整体的时间复杂度是O(n)

如果function是这样：

void function(int count)
{
    int j;
    for(j = count;j < n;j++)
    {
        //时间复杂度为O(1)的程序步骤程序
    }
}

这和前面的例子一样，只不过是把嵌套内循环放到了函数中，所以最终的时间复杂度为O(n²)

例子2

n++;//执行次数为1
function(n);//执行次数为n
int i,j;
for(i = 0;i < n;i++)//执行次数为n²
{
    function(i);
}
for(i = 0;i < n;i++)//执行次数为n(n+1)/2
{
    for(j = i;j < n;j++)
    {
        //时间复杂度为O(1)的程序步骤程序
    }
}