数据结构（一）：结构概念与算法概念及时间复杂度

超、凢脫俗 2021-08-19 23:28 448阅读 0赞

## 数据结构概念 ##

*  **数据结构分为：逻辑结构、物理结构**

### 逻辑结构 ###

*  集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系
 *  线性结构：数据元素之间是一对一的关系
 *  树形结构：树形结构中元素之间存在一种一对多的层次关系
 *  图形结构：元素是多对多的关系

### 物理结构（存储结构） ###

*  **顺序存储：把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的**
 *  **链式存储：把数据元素存放在任意存储单元里，这组存储单元可以是连续的，也可以是不连续的，通过指针找到下一个存放的地址**

## 算法概念 ##

*  假设现在要写一个求1+2+3+4+…..+100的程序

int num = 0;
    for (int i=1;i<=100;i++){
        num+=i;
    }
    System.out.println(num);

*  上面算法需要循环100次，当要求加到100000时，循环次数越多计算结果越慢，而采用高斯算法

int sum = 0, i = 1000000;
    sum = (1 + i) * i / 2;
    System.out.println(sum);

![9434708-4fca1e4b90896839.png][]

yBeXK.png

### 算法效率度量方法 ###

*  事后度量法：通过计算算法开始时间与结束时间
 *  事前分析估算法：**分析程序执行代码次数（行数）**，优秀的算法相比普通算法根据问题输入规模 n 的大小，随着 n 的值越大，时间效率上的差异就越大

### 函数的渐进增长 ###

*  假设有算法A与算法B：
    
     *  算法A----要做2n+3次操作（如执行完一个n次的循环，然后又执行一个n次的循环，最后执行3次赋值运算）
     *  算法B----要做3n+1次操作
     *  当 n>2 时，算法A就开始优于算法B，随着时间增加，算法A比算法B越来越好
 *  在实际算法变化中，我们常忽略这些加法常数

### 算法时间长度 ###

*  更多的例子：[http://blog.csdn.net/zolalad/article/details/11848739][http_blog.csdn.net_zolalad_article_details_11848739]
 *  在进行算法分析时
    
     *  算法执行次数写为T（n），n是问题规模
     *  从而推导算法时间复杂度记作：T(n) = O(f(n))
     *  用大写的O( )体现算法时间复杂度，随着n增大，T(n)增长最慢为最优算法

### 推导大O的方法 ###

*  用常数1取代运行时间中所有加法常数
 *  在修改后的运行次数函数中，只保留最高阶项
 *  如果最高阶项存在且不是为1，则去除常数项

#### 常数阶 ####

*  该算法运行次数为 f(n) = 3，根据推到大O方法，将常数项3改为1，该算法时间复杂度为 O(1)

int sum = 0, i = 1000000;   /*执行一次*/
    sum = (1 + i) * i / 2;      /*执行一次*/
    System.out.println(sum);    /*执行一次*/

#### 线性阶 ####

*  确定算法的阶次，分析算法的复杂度，关键是分析循环结构的运行情况，下面代码时间复杂度为 O(n)，因为循环体中的代码要执行 n 次

int i,n =100;
    for (i=0;i<n;i++){
        //....
    }

#### 对数阶 ####

*  下面代码每次会执行直到 count > n，每次执行完 count 会乘以 2，得 2的x次方=n 得到 x=log2n，该循环复杂程度为O(logn)

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

#### 平方阶 ####

*  单个循环时间复杂度为 O(n)，而在循环嵌套内两个循环都执行 n ，则为 O(n的2次方)，如下面代码

int i,j,n = 200;
    for(i = 0;i < n;i++){
        for（j = 0;j < n;j++）{
            // 时间复杂度为平方阶 O(n的2次方)
        }
    }

*  若外循环次数为m，内循环次数为n，则时间复杂度为 O(m\*n)

int i, j, m = 300, n = 200;
    for (i = 0; i < m; i++) {
        for (j = 0; j < n; j++) {
            // 时间复杂度为 O(m*n)
        }
    }

*  下面代码调用了一个函数，函数的时间复杂度为O(1)，所以整体时间复杂度为O(n)

public static void main(String[] args){
        int i,n = 200;
        for(i = 0;i < n;i++){
            fun();
        }
    }
    public static void fun(){
        System.out.println();
    }

## 常见的时间复杂度 ##

*  复杂度大小顺序为：O(1) < O(logn) < O(n) < O(nlogn) < O(n的平方) < O(n的立方) < O(2的n次方) < O(n!) < O(n的n次方)

<table> 
 <thead> 
  <tr> 
   <th style="text-align:center">执行次数函数</th> 
   <th style="text-align:center">阶</th> 
   <th style="text-align:center">非正式术语</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="text-align:center">12</td> 
   <td style="text-align:center">O(1)</td> 
   <td style="text-align:center">常数阶</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">2n+3</td> 
   <td style="text-align:center">O(n)</td> 
   <td style="text-align:center">线性阶</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">3*(n平方)+2n+1</td> 
   <td style="text-align:center">O(n的平方)</td> 
   <td style="text-align:center">平方阶</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">5log2n+20</td> 
   <td style="text-align:center">O(logn)</td> 
   <td style="text-align:center">对数阶</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">2n+3nlog2n+19</td> 
   <td style="text-align:center">O(nlogn)</td> 
   <td style="text-align:center">nlogn阶</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">6<em>n的3次方+2</em>n的平方+3n+4</td> 
   <td style="text-align:center">O(n的立方)</td> 
   <td style="text-align:center">立方阶</td> 
  </tr> 
  <tr> 
   <td style="text-align:center">2的n次方</td> 
   <td style="text-align:center">O(2的n次方)</td> 
   <td style="text-align:center">指数阶</td> 
  </tr> 
 </tbody> 
</table>

[9434708-4fca1e4b90896839.png]: /images/20210811/5f67152fb1eb4cb9a8aec8868a0e0f7e.png
[http_blog.csdn.net_zolalad_article_details_11848739]: https://link.jianshu.com?t=http%3A%2F%2Fblog.csdn.net%2Fzolalad%2Farticle%2Fdetails%2F11848739