绪论(一)


绪论(一)

程序设计 = 数据结构 + 算法
程序设计的实质是对确定的问题选择一种好的数据结构,加上设计一种好的算法。

数据结构

数据元素:数据的基本单位,有时还称为元素、记录、结点、顶点。
数据项:数据不可分割的最小单位。
一个数据元素可由多个数据项构成。
数据对象:由性质相同(类型相同)的数据元素组成的集合。
数据类型:一个值的集合和定义在这个值上的一组操作的总称

  1. 原子类型。int,char,float等。
  2. 结构类型。线性表、数组、树等。

数据结构英文Data Structure,通俗点来说,数据结构就是数据元素之间存在的一种或多种特定关系的集合
数据元素之间的关系称为结构

数据结构分为逻辑结构物理结构

  • 逻辑结构:数据对象中数组元素之间的相互关系
  • 物理结构:数据的逻辑结构在计算机中的存储方式,就是研究如何将数据元素存储到计算机的存储器中

逻辑结构

逻辑结构有四种基本类型:集合结构线性结构树形结构图形结构
也可以统一的分为线性结构非线性结构

  1. 集合结构:集合结构中数据元素除了同属于一个集合外,它们之间没有任何其他关系
  2. 线性结构:线性结构中的数据元素是一对一的关系
  3. 树形结构:树形结构中的数据元素之间存在一种一对多的关系
  4. 图形结构:图形结构的数据元素是多对多的关系
  • 线性结构
    1. 线性表
    2. 队列
    3. 数组、广义表
    4. 字符串
  • 非线性结构
    1. 树,二叉树

物理结构

  1. 顺序存储结构:数据元素存放在地址连续的存储单元中,数据间的逻辑关系和物理关系一致,例如:C/C++中的数组
  2. 链式存储结构:数据元素存放在任意的存储单元中,这组存储单元可以连续也可以不连续,需要用一个指针存放数据元素的地址,这样就可以通过地址找到相关元素的位置

算法

假如要计算1+2+3+……+100,以下两种算法哪种更高效?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stdio.h>
int main()
{
//第一种算法
int i,sum=0,n=100;
for(i=1;i<n;i++)
{
sum=sum+i;
}
printf("%d",sum);
//第二种算法
int i,sum=0,n=100;
sum=(1+n)*n/2;
printf("%d",sum);
return 0;
}

算法
就是解决特定问题求解步骤的描述,表现为指令的有限序列,每条指令表示一个或多个操作,打个比方,算法就是你打游戏时为了通关而使用的方式和技巧。
对于给定的问题,可以用多种算法来解决,就像让你连接两个点,你可以用直线连接也可以用曲线连接。
一个算法也不可能具有解决所有问题的能力。

算法的特性

  • 输入
    • 算法具有零个或多个输入
  • 输出
    • 算法至少有一个或多个输出,输出形式可以是打印输出,也可以是返回一个值或多个值
  • 有穷性
    • 算法在执行有限步骤后,自动结束而不会无限循环,且每一个步骤在可接受的时间内完成
  • 确定性
    • 算法每一步骤都具有确定的含义,不会出现二义性
  • 可行性
    • 算法每一步都必须是可行的。

算法设计的要求

  • 正确性:算法至少应该具有输入、输出和加工处理无歧义性、能正确反应问题需求,正确得到问题的正确答案,大体分为下列四种层次
    1. 没有语法错误
    2. 对n组输入产生正确结果
    3. 对特殊输入产生正确结果
    4. 对所有输入产生正确结果
  • 可读性:方便阅读,理解和交流
  • 健壮性:输入数据不合法时,算法也能做出相关处理,而不是产生异常或莫名其妙的结果
  • 时间效率高和存储量低

算法的分析

一般包括时间复杂度的分析和空间复杂度的分析,重点往往在于时间复杂度的分析部分。
通常用时间复杂度指运行时间的需求,用空间复杂度指空间的需求。
复杂度通常指时间复杂度

时间复杂度

同一个算法在不同语言,不同编译程序,不同计算机实现时,效率均不相同,所以我们往往只关注算法的时间开销相对于问题规模变化的趋势,也就是时间复杂度
设n为求解的问题规模,基本操作(或语句)执行次数总和称为语句频度,记做f(n)。
执行以下步骤:

  1. 去掉f(n)中的所有加法常数。
  2. 只保留最高项阶。

时间复杂度记做T(n),T(n)=O(f(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
46
47
48
49
50
51
52
53
54
55
//例1:
{
int a;
scanf("%d",&a);
a++;
printf("%d",a);
}
//语句频度为:f(n)=f(1)=3
//时间复杂度为:T(n)=O(f(n))=O(3)=O(1)
//O(1)称为常量阶/常量数量级

//例2:
void sum(int a[],int n)
{
int s=0,i; //1
for(i=0;i<n;i++) //n
s=s+a[i]; //n
printf("%d",s); //1
}
//语句频度为:f(n)=1+n+n+1
//时间复杂度为:T(n)=O(f(n))=O(2n+2)=O(n)
//O(n)称为线性阶/线性数量级

//例3:
void sum(int n)
{
int s=0,i,j; //1
for(i=1;i<=m;i++) //m
{
for(j=1;i<=n;j++) //m*n
s++; //m*n
printf("%d",s) //m
}

}
//语句频度为:f(m,n)=2mn+2m+1
//当m=n时,f(n)=2n^2+2n+1
//T(n)=O(f(n))=O(2n^2+2n+1)=O(n^2)
//O(n^2)称为平方阶/平方数量级
//例4:
void sum(int n)
{
int s=0,i,j; //1
for(i=1;i<=n;i++) //n
{
for(j=1;i<=i;j++) //?
s++; //?
printf("%d",s) //n
}

}
//循环主体执行次数为:1+2+……+n=n(1+n)/2
//算法频度为:f(n)=1+n+n(1+n)+n=n^2+3n+1
//T(n)=O(f(n))=O(n^2)
//O(n^2)称为平方阶/平方数量级

常见的时间复杂度
O(1) < O(log2 x) < O(n) < O(nlog2 n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < o(n^n)
最坏情况运行时间是一种保障,就是运行时间不会再坏了。
平均情况就是平均运行时间,是所有情况中最有意义的,它是期望的运行时间。
通常除非特别指定,我们提到的运行时间都是最坏情况时间复杂度。

空间复杂度

占用存储单元的长度。


Author: ljs
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source ljs !
评论
  TOC