数据结构的基本概念和算法评价_数据结构基本概念与算法评价

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

文章目录

---

前言

例如：随着计算机的不断发展，数据结构这门技术也越来越重要，很多人都开启了学习数据结构，本文就介绍了数据结构的基础内容。

一、数据结构的基本概念

1.1.1基本概念和术语

• 数据

• List item

  数据是信息的载体，是描述客观事物的属性的数，字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合，数据是计算机程序加工的原料。

• 数据元素

• List item

  数据元素是数据的基本单位。

• 数据对象
  数据对象是具有相同性质的数据元素的集合。是数据的一个子集。

4. 数据类型
   数据类型是一个值的集合和定义在此此集合上的一组操作的总称。
   1）原子类型 。 其值不可再分的数据类型。
   2）结构类型 。 其值可以再分解为若干成分的数据类型。
   3）抽象数据类型。 抽象数据组织及与之相关的操作。
5. 数据结构
   数据结构是相互之间存在一种或几种特定关系的数据元素的集合。

1.1.2 数据结构的三要素

1. 数据的逻辑结构
   1）线性结构：线性表，栈，队列。
   2）非线性结构：树，图，集合。

2. 数据的存储结构(物理结构)
   1）顺序存储 逻辑上相邻物理位置也相邻，用存储单元的物理位置邻接关系体现。
   2）链式存储 逻辑相邻物理上可以不相邻，用指针体现。
   3）索引存储
   4）哈希存储

运算的定义是针对逻辑结构的，指出运算的功能。
运算的实现是针对物理结构的，指出运算的步骤。

程序等于数据结构+算法。

算法：是对特定问题求解步骤的一种描述，是指令的有限序列，其中每条指令表示一个或多个操作。

算法的五个特性

1）有穷性
2）确定性
3）可行性
4）输入
5）输出
1
2
3
4
5

"好算法"特质：

1）正确性
2）可读性
3）健壮性
4）高效率和低存储量需求
1
2
3
4

加法：多项保留，只保留最高阶的项，且系数变为1。
乘法：多项相乘都保留。

常对幂指阶：
O(1)<O(log2n)<O(n)<O(nlog2n)<O(n^2)<O(n3)<O(2^n)<O(n!)<O(nn)

List item

结论：

		1）顺序执行的代码只会影响常数项，可以忽略。
		2）只需挑取循环中一个基本操作分析它的执行次数与n的关系即可。
		3）如果有多层嵌套循环，只需关注最深层循环循环了几次。
1
2
3

三种复杂度

• 最好时间复杂度

第一个是期望值O(1)

• 最坏时间复杂度

最后一个是期望值 O(n）

• 平均时间复杂度

任何数字查找的平均代价是O(n)

二、算法评价

1.简单时间复杂度

代码如下（示例）：

1. 下面程序的时间复杂度为（A）。

下面程序的时间复杂度为（）。

for(i = 0; i < m; i++)
      for(j = 0; j < t; j++)
           c[i][j] = 0;
for(i = 0; i < m; i++)
      for(j = 0; j < t; j++)
            for(k = 0; k < n; k++)
                 c[i][j] = c[i][j]+a[i][k] * b[k][j];

A.
O(m × n × t)


B.
O(m + n + t)


C.
O(m + n × t)


D.
O(m × t + n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

数据在计算机内存中的表示是指（A） 。


A.
数据的存储结构


B.
数据结构


C.
数据的逻辑结构


D.
数据元素之间的关系
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

数据结构是一门研究非数值计算的程序设计问题中计算机的（A）以及它们之间的关系和运算等的学科。


A.
操作对象


B.
计算方法


C.
逻辑存储


D.
数据映象
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

有以下算法，其时间复杂度为（C ）。

void fun(int n){
    int i=0;
    while(i*i*i<=n)
        i++;
}

A.O(n)
B.O(nlogn)
C.O( ³√n)
D.O(n)
1
2
3
4
5
6
7
8
9
10
11
12

程序段如下： D

>∑(2,n-1)∑(1,i-1)1=∑(2,n-1)(i-1)=(n-2)(n-1)/2=O(n^2)

for(i=n-1;i>1;i--)
    for(j=1;j<i;j++
if(A[j]>A[j+1]){
    t=A[j];
    A[j]=A[j+1];
    A[j+1]=A[j];
    }

A.O(n)
B.O(nlogn)
C.O(n^3 )
D.O(n^2 )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

算法分析(应用)

下面 SumPower 函数的时间复杂度为 ▁▁▁E▁ 。

double SumPower(double x, int n)
{
    double y = 0.0, p = 1.0;
    int k;
    for (k = 1; k <= n; ++k)
    {
        p *= x;
        y += p;
    }
    return y;
}

A.O(n^2 )

B.O(2^n )

C.O(log2n)

D.O(nlog2n)

E.O(n)

F.O(1)

G.O(√n)

H.O(n√n )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

下面程序段的时间复杂度是 ( D)

i ＝ 0；
while（i<=n）
     i = i * 3；

A.O(2n)

B.O(n)

C.O(n^2 )

D.O(log3n)
1
2
3
4
5
6
7
8
9
10
11
12
13

下面 SumPower 函数的时间复杂度为 ▁▁D▁▁▁ 。

> 看 for循环中自变量的变化

double Power(double x, int n)
{
    double y = 1.0, p = x;
    int t = n;
    for (t = n; t > 0; t /= 2)
    {
        if (t % 2)
        {
            y *= p;
        }
        p *= p;
    }
    return y;
}

double SumPower(double x, int n)
{
    double y = 0.0;
    int k;
    for (k = 1; k <= n; ++k)
    {
        y += Power(x, n);
    }
    return y;
}

A.O(n^2)

B.O(2^n )

C.O(log2n)

D.O(nlog2n)

E.O(n)

F.O(1)

G.O(n)

H.O(n^n​)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

下面算法的时间复杂度为 ▁▁▁▁▁C。
int foo(int n)
{
    int i, s = 0;
    for (i = 1; i * i <= n; ++i)
    {
        s += i;
    }
    return s;
}
A.O(n^2 )

B.O(n)

C.O(√n)

D.O(log2n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

数据采用链式存储结构时，要求( A)


A.每个节点占用一片连续的存储区域

B.所有节点占用一片连续的存储区域

C.节点的最后一个数据域一定是指针类型

D.每个节点有多少个后继就设多少个指针域
1
2
3
4
5
6
7
8
9
10

使用渐近性来表示算法复杂度的原因是（C ）。


A.可以精确表示算法的复杂度

B.算法的复杂度无法使用时间单位来表示

C.研究者更关心算法的增长趋势

D.我们只研究小规模问题
1
2
3
4
5
6
7
8
9
10

下面 Power 函数的时间复杂度为 ▁▁▁▁C。

double Power(double x, int n)
{
    double y;
    if (n > 0)
    {
        y = Power(x, n / 2);
        y *= y;
        if (n % 2)
        {
            y *= x;
        }
    }
    else
    {
        y = 1.0;
    }
    return y;
}

A.O(n^2 )

B.O(2^n )

C.O(log2n)

D.O(nlog2n)

E.O(n)

F.O(1)

G.O(n)

H.O(n^n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

• 递归程序-----采用分治策略(用公式进行递推)

• “分”：将大问题大致分为两个主文相等的幂次阶子问题，用递归求解。

• “治”：将两个子问题的解合并到一起，并可能再做一些附加工作，得到问题的解。

• 主方法：大小为n的问题分成若干个大小为n/b的子问题，其中a个问题需求解。

• 而Cnk 是合并各个小问题需要的工作量。

•  	Tn={c,n=1;
  1

•  aT(N/b)+Cnk,n>1}
  1

• `推导

T(1)=1
T(N)=2T(N/2)+O(N)
1)等号右边连续带入递归关系
T(N)=2T(N/2)+N
=2(2T(N/4)+N/2)+N
=2{2[2T(N/8)+N/4]+N/2}+N
=2^kT(N/2^k)+kN
由K=log2n
T(N)=NT(1)+NlogN=NlogN+N
2)叠缩求和 用N条递归关系两边不断交换
T(N)/N=T(N/2)/N/2+1
T(N/2)/N/2=T(N/4)/N/4+1
T(2)/2=T(1)/1
左边所有项相加＝右边所有项相加
T(N)/N=T(1)/1+logN
T(N)=NlogN+N
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.空间复杂度

• 算法原地工作：算法所吸引要的额外辅助空间为常量。

总结

常见算法时间复杂度

	描述		增长的数量级			说明				举例
	常数级		0(1)			普通语句			两数相加
	对数级		0(logN)			二分策略			二分查找
	线性级		0(N)			单层循环			找出最大元素
	线性对数级		0(NlogN)	分治策略			归并排序
	平方级		0(N^2)			双层循环			检查所有元素对
	立方级		0(N^3)			三层循环			检查所有三元组
	指数级		0(2^N)			穷举查找			检查所有子集
	
	
1
2
3
4
5
6
7
8
9
10

以上就是今天要讲的内容，本文仅仅简单介绍了数据结构的概念以及时间复杂度的求法。