数据结构与算法概念解析【一】_梧桐树下的温柔的专栏文章_微信文章

数据结构的是三个方面

        数据的逻辑结构：  线性结构-->线性表，栈，队列
                        非线性结构-->树形结构，图形结构
                        
        
        数据的存储结构：  顺序结构，链式结构
        
        
        数据的运算：      检索，排序，插入，删除，修改
复制代码

数据间的相互关系称为逻辑结构，通常为四种逻辑结构：

1，集合：结构中的数据元素除了同属于一种类型外，别无其他关系。

2，线性结构：结构中的数据元素之间存在一对一的关系。

3，树形结构：结构中的数据元素之间存在一对多的关系。

4，图形结构：结构中的数据元素之间存在多对多的关系。

数据结构在计算机中有俩种存储方法：

1，顺序存储：用数据在存储器中的相对位置来表示他们之间的关系

2，链式存储：在每个数据元素之间增加一个存放地址的指针，来表示他们之间的逻辑关系

时间复杂度

一个算法花费的时间与算法中的语句的执行次数成正比，哪个算法中执行次数多，花费时间就越多，一个算法中的语句执行次数成为他的时间频度，简称为频度，记作：T(n)

一般情况下，算法中操作重复执行的次数是问题规模n的一个函数，用T(n)来表示，若有某个辅助函数f(n)使得当n趋于无穷大时，总有T(n)/f(n)的极限值为不等于0的一个常数，则称：f(n)为T(n)的同数量级函数，记作T(n)=O(f(n))，称O(f(n))为算法的渐进时间复杂度，简称为时间复杂度。

常见的时间复杂度之间的关系为：

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(2ⁿ)<O(n!)<O(nⁿ)

时间复杂度的计算方法：

所有算法语句执行的总次数相加的结果，去掉常数项，只保留最高阶项，就是最终的时间复杂度。

示例1

    sum=0  //(1)
    
    for(int i=0; i<n; i++){  //(2)
        for(int j=0;j<n;j++){  //(3)
            sum++           //(4)
        }
    }
复制代码

语句（1）执行的次数为1次

语句（2）执行的次数为n次

语句（3）执行的次数为n²次

语句（4）执行的次数为n次

得出结论：该算法的时间复杂度为 1+n+n²+n ==> O(n²)

示例2：

    a=0; b=1;  //(1)
    for(int i=0;i<n;i++){ //(2)
        s=a+b;   //(3)
        b=a;    //(4)
        a=s;    //(5)
    }
复制代码

语句（1）执行的次数为1次

语句（2）执行的次数为n次

语句（3）执行的次数为n次

语句（4）执行的次数为n次

语句（5）执行的次数为n次

得出结论：该算法的时间复杂度为 T(n)==1+n+n+n+n=O(n)

示例3

    i=1;    //(1)
    while(i<=n){  
        i= i* 2;
    }
复制代码

语句（1）执行的次数为1；

语句（2）执行的次数未知，设为 f(n)

可以得出： 2f(n)<=n 所以 f(n) = log2ⁿ

该算法的时间复杂度为 T(n)=log2ⁿ

空间复杂度

S(n) = O(f(n))

一个算法在计算机存储器上占用的存储空间包括存储算法本身占用的空间，算法的输入输出数据占用的空间，和算法在运行过程中临时占用的存储空间这三个方面。

存储算法所占用的存储空间与算法书写的长短成正比，要压缩着方面的存储空间，就必须编写出较短的算法。