好多编程入门C语言&嵌入式嵌入式 Linux C ARM

混子数据结构学习之第一章绪论笔记下

2021-11-09  本文已影响0人  那个混子

"磨棱角,褪优越,沉下心"
"不止于心动,更付诸于行动,执行力!“

引言

本章接着前面的绪论记录,本章主要记录算法相关的基本概念。在这里只记录一些核心需要掌握的东西了。

算法与算法分析

算法定义

算法是对特定问题求解方法和步骤的一种描述,它是指令的有限序列。其中每个指令表示一个或多个操作。算法就是解决问题的方法和步骤。

算法的特性

算法设计的要求

算法分析与评估

对于同一个问题,可能有许多种不同的方法,也就是有许多种算法,需要衡量评估哪种方法好,择优问题。

算法效率

算法效率以下两个方面来考虑:

算法时间效率的度量

算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量。

(1)度量方法
事前分析方法:

方法:算法运行时间=一个简单操作所需的时间*简单操作次数。

算法运行时间=Σ每条语句的执行次数*该语句执行一次所需的时间。

每条语句的执行次数又称为语句频度

算法运行时间=Σ每条语句频度*该语句执行一次所需的时间

实际评估算法时间效率,并不需要很明确知道每条语句执行的时间,这里运用高数上面的极限、等价相关的思想,直接简化只用执行的次数来衡量算法的时间效率了。
下面是资料的相关描述:
每条语句执行一次所需的时间,一般是随机器而异的。取决于机器的指令性能、速度以及编译的代码质量。是由机器本身软硬件环境决定的,它与算法无关。所以,我们可假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可转化为讨论该算法中所有语句的执行次数,即频度之和了。这就可以独立于不同机器的软硬件环境来分析算法的时间性能了。

例子:
两个n*n矩阵相乘的算法

//两个n*n矩阵相乘的算法
for(i = 1; i <= n; i++){//n+1次 
    for(j = 1; j <= n; j++){//n(n+1)次 
        c[i][j] = 0;//n*n次 
        for(k = 0; k < n; k++){//n*n*(n+1)次 
            c[i][j] = c[i][j] + a[i][k] * b[k][j];//n*n*n次 
        }
    }
}
上述的算法时间消耗可表示为

时间复杂度

背景:

若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)= O(f(n)),称O(f(n))为算法的渐进时间复杂度(O是数量级的符号),简称时间复杂度。
对于求解矩阵相乘问题,算法耗费时间: T(n)= 2n3+ 3n2+2n+1。
上面例子中T(n)和n3具同阶或同数是级,引入大"O记号,则T(n)可记作:T(n)=0(n3)。

算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作:

T(n) = O(f(n))

基本语句是算法中重复执行次数和算法的执行时间成正比的语句;对算法运行时间的贡献最大;执行次数最多。
n越大算法的执行时间越长(排序:n为记录数;矩阵:n为矩阵的阶数;多项式:n为多项式的项数;集合:n为元素个数;树:n为树的结点个数;图:n为图的顶点数或边数)。

计算时间复杂度

一般情况下,不必计算所有操作的执行次数,而只考虑算法中基本操作执行的次数,它是问题规模n的某个函数,


忽略低次项和高次项的系数,体现增长率的含义

方法步骤

例子:(一些例子涉及到高数的级数了,很陌生了,头疼,先暂时忽略)

void exam(float x[][], int m, int n)
{
    float sum[];
    for(int i = 0; i < m; i++)   //执行m+1次
    {
        sum[i] = 0.0;
        for(int j = 0; j < n; j++)//执行(n+1)*m次
        {
            sum[i] += x[i][j];//嵌套最深层语句  执行m*n次
        }
    }
    for(i = 0; i < m; i++)
    {
        cout << i << ":" << sum[i] << endl;
    }
}

f(n)= m*n;
时间复杂度表示为:T(n)= O(m*n);
for(i = 1; i <= n; i++){
    for(j = 1; j <= i; j++){
        for(k = 1; k <= j; k++){
            x = x + 1;
        }
    }
}

下面这个是考研的真题:

//分析以下程序段的时间复杂度
i = 1;//语句1
while(i <= n){
    i = i * 2;//语句2
}

复杂度比较

小结

基本到这里就结束了绪论的学习,大概记录这些了!

参考资料:
青岛大学.王卓.数据结构与算法
《数据结构 C语言版》.严蔚敏

欢迎关注本人微信公众号:那个混子
记录自己学习的过程,分享乐趣、技术、想法、感悟、情感!
单片机类嵌入式交流学习可加企鹅群:120653336
上一篇 下一篇

猜你喜欢

热点阅读