算法分析（概论）

本文主要是介绍算法分析（概论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

第一章 概论

1.算法的概念

1.定义

2.算法设计要求

3.算法的特性

4.算法描述

5.数据结构与算法

6.算法设计的基本步骤

2.算法分析

1.计算机资源

2.算法分析

3.评判算法效率的方法

4.算法时间复杂度分析

5.渐进符号

1.大Ο符号

2.大Ω符号

3.大Θ符号

4.三种符号图例

5.渐进符号特性 

---

第一章 概论（上）

1.算法的概念

1.定义

算法是求解问题的一系列计算步骤，是来将输入数据转换成输出结果。

用于将输入数据转换为输出结果。

2.算法设计要求

①正确性：要求算法能够正确地执行预先规定的功能和性能要求。

②可使用性：要求算法能够很方便的使用。（用户友好性）

③可读性：算法应该易于人的理解。（可读性好：算法的逻辑必须是清晰的、简答的和结构化的）

④健壮性：要求算法具有很好的容错性，也就是可以提供异常处理，能够对不合理的数据进行检查，不经常出现异常中断或死机现象。

⑤高效性与低存储量需求：通常算法的效率主要指算法的执行时间。对同一个问题如果有多种算法求解，执行时间短的算法效率高。（算法存储量指的是算法执行过程中所需的最大存储空间，效率和低存储量都与问题的规模有关）

举个例子：关于在带头结点的单链表h中查找第一个值为x的结点，并返回其逻辑序号（从1开始），找不到则返回0。

#include<stdio.h>
typedef struct node
{int data;struct node *next;
}LNode;
int Findx(LNode *h,int x)
{int i=0;LNode *p=h->next;while(p->data!=x&&p!=NULL){p=p->next;i++;}if(p==NULL){return 0;} else{return i;}
}

3.算法的特性

①有限性：一个算法必须总是（对任何合法的输入值）在执行有限步之后结果，且每一步都可在有限时间内完成。

②确定性：算法每一步指令必须有确切的含义，不会产生二义性。

③可行性：算法中的每一条运算都必须是足够基本的，也就是它们在原则上都能精确的执行，甚至人们仅用笔和纸做有限次运算就可以完成。

④输入性：一个算法有零个或者多个输入。大部分算法的输入参数是必要的，但对于较简单的算法，可以不需要任何输入参数（例如1+2）。因此算法可以是一个或者多个。

⑤输出性：一个算法可以有零个或者多个输出。算法用于某种数据的处理，如果没有输出，这样的算法是没有意义的，这些输出是和输入有着某些特定关系的量。

错误举例：

//举例1:不满足算法的有限性（无限循环）
void main()
{int n=2;while(n%2==0){n+=2;}printf("%d\t",n);
}
//举例2:不满足算法的可行性（分母为0）
void main()
{int x,y;x=0;y=5/x;printf("%d,%d",x,y);
}

4.算法描述

C语言可以使用指针方式实现形参的回传；

C++语言使用引用型参数的概念，引用型参数名前需要添加&，表示这样的形参在执行后会将结果回传给对应的实参。

//C
bool fun(int n,int s)
{if(n<=0){return false;}s=0;for(int i=1;i<=n;i++){s+=i;}return true;
}
void main()
{int a=10,b=0;if(fun(a,b)){printf("%d",b);}else{printf("输入错误！");}
}
//C++
bool fun(int n,int &s)
{if(n<=0){return false;}s=0;for(int i=1;i<=n;i++){s+=i;}return true;
}

5.数据结构与算法

数据结构是算法设计的基础，算法的操作对象是数据结构。

数据结构设计主要是选择数据的存储方式（例如确定求解问题中的数据采用数组存储还是采用链表存储）；算法设计就是在选定的存储结构上设计一个满足要求的好的算法。

数据结构关注的是数据的逻辑结构、存储结构以及基本操作；算法关注的是如何在数据结构的基础上解决实际问题。

算法是编程思想，数据结构是思想的逻辑基础。

6.算法设计的基本步骤

①分析求解问题：确定求解问题的目标（功能）、给定的条件（输入）、生成的结果（输出）

②选择数据结构和算法设计策略：设计数据对象的存储结构，因为算法效率取决于数据结构的存储表示。算法设计策略包括迭代法、分治法、动态规划和回溯法等

③描述算法：清步骤晰准确记录所设计的求解

④证明算法的正确性：可以采用数学证明方法

⑤算法分析：在多个算法中选取最好的算法

2.算法分析

1.计算机资源

①计算时间②内存空间。

2.算法分析

是分析算法占用计算机资源的情况，算法分析包括：①时间复杂度②空间复杂度，目的在于考察算法的时间和空间效率，以求改进算法或对不同算法进行比较。

3.评判算法效率的方法

①事后统计法（必须执行程序）②事前分析估算法（存在其他因素掩盖算法本质）

4.算法时间复杂度分析

1. 时间复杂度分析：在计算机上运行时所消耗的时间与很多因素有关，仅考虑算法本身的效率高低，可以认为一个特定算法的“运行工作量”的大小只依赖于问题的规模，或者是问题规模的函数。这就是事前分析估算法。一个算法是由控制结构（顺序、分支、循环）和原操作（指固定数据类型的操作）构成。算法的执行时间主要与问题规模有关。

2. 分析算法时间复杂度的一般步骤：算法→分析问题规模n，找出其中的基本语句，求出其运算次数f（n）→用大Ο，大Ω或Θ表示（大Ο，大Ω或Θ是渐进符号，采用渐进符号表示的算法时间复杂度也称为渐进时间复杂度，反映的是一种增长趋势）

3. 通常称渐进时间复杂度为多项式的算法为有效算法；称n！或2^n这样的低效算法为指数时间算法。

5.渐进符号

1.大Ο符号

定义1（大〇符号）：f（n）=O（g（m））（读作“ （n）是g（n）的大O”），当且仅当存在正常量c和no，使当n≥n。时f（n）≤cg（m），即g（n）为f（n）的上界。

2.大Ω符号

定义 2(大Ω符号):f(n)=Ω(g(n))(读作“f(n)是g(n)的大Ω”),当且仅当存在正常量c和n,使当 n>no 时 f(n)>cg(n),即 g(n)为 f(n)的下界。

3.大Θ符号

定义 3(大 @ 符号):f(n)= @(g(n))(读作“f(n)是g(n)的大@”),当且仅当存在正常量 c、c: 和 no,使当 n>n 时有 cg(n)<f(n)<cg(n),即 g(n)与 f(n)的同阶。

4.三种符号图例

在每个部分中，n0是最小的可能值，大于n0的值也有效，成为渐进分析。Θ(g(n))对应的g(n)是渐进确界，O(g(n))对应的g(n)是渐进上界，Ω(g(n))对应的g(n)是渐进下界。

5.渐进符号特性 

这篇关于算法分析（概论）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---