虾皮网站有的做吗,网站建设维护合同书,创意网站界面,网站 后台 开发目录
一、算法
1.基本概念
2.描述方法
3.算法效率
二、算法的时间复杂度
三、算法的空间复杂度 一、算法
1.基本概念
通俗的讲#xff0c;算法是解决问题的方法#xff0c;比如在现实生活中一道菜谱#xff0c;一个安装轮椅的操作指南等。
严格的说#xff0c;算法…目录
一、算法
1.基本概念
2.描述方法
3.算法效率
二、算法的时间复杂度
三、算法的空间复杂度 一、算法
1.基本概念
通俗的讲算法是解决问题的方法比如在现实生活中一道菜谱一个安装轮椅的操作指南等。
严格的说算法是对特定问题求解步骤的一种描述是指令的有限序列。
算法具有的基本特性有 1有穷性。一个算法必须总是在执行有穷步之后结束且每一步都在有求时间内完成。 2确定性。算法中的每一条指令必须有确切的含义不存在二意性。 3可行性。这个算法是可执行的。并且算法的每一条指令都可以被分解为基本的可执行的操作步骤。 一个“好”算法还具有正确性健壮性可理解性抽象分级高效性等特性。
2.描述方法
算法的描述方法可以将所设计算法中设计的求解步骤记录下来。常用的描述算法的方法有自然语言、流程图、程序设计语言和伪代码等。
3.算法效率
如何衡量一个算法的效率 每当算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。 时间复杂度 主要衡量一个算法的运行快慢。 空间复杂度 主要衡量一个算法运行所需要的额外空间。 二、算法的时间复杂度 撇开与计算机应硬软件有关的因素影响算法时间代价的最主要因素是问题规模。所以运行算法所需要的时间T就是问题规模n的函数记作 T(n)。它定量描述了该算法的运行时间。 一 个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。 为了客观的反映一个算法的执行时间。可以用算法中基本语句的执行次数来度量算法的工作量基本语句是执行次数与整个算法执行次数成正比的语句。 只考察当问题规模充分大时。算法中基本语句的执行次数在渐进意义下的阶称作算法的渐进时间复杂度。简称为时间复杂度。 简而言之一个算法所花费的时间与其中基本语句的执行次数成正比例算法中的基本操作语句的执行次数为算法的时间复杂度。到某条基本语句与问题规模n之间的数学表达式就算出了该算法的时间复杂度。 但是有时我们在计算基本语句的执行次数时可能会发现有些次数计算时非常麻烦。所以实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么就需要使用大O的渐进表示法。 大O的渐进表示法 大O符号Big O notation是用于描述函数渐进行为的数学符号。 推导大O阶方法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 举例计算时间复杂度
void Func(int N)
{int count 0;for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}这里的问题规模是N基本语句为count基本操作次数为F(N)2N10那么有大O的渐进表示法就为O(n)。
常见的时间复杂度有 三、算法的空间复杂度 空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。 空间复杂度不是算程序占用了多少字节的空间而算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似也使用大O的渐进表示法。
算法在运行过程中所需的存储空间包括
①输入输出数据占用的空间;②算法本身占用的空间③执行算法需要的辅助空间。
其中输人输出数据占用的空间取决于问题与算法无关算法本身占用的空间虽然与算法相关但一般其大小是固定的。所以算法的空间复杂度是指算法在执行过程中需要的辅助空间数量也就是除算法本身和输人输出数据所占用的空间外,算法临时开辟的存储空间。 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候申请的额外空间来确定。 举例1计算空间复杂度
void Bubble_sort(int arr[], int sz)
{int i 0;for (i 0; i sz - 1; i){int flag 0;int j 0;for (j 0; j sz - 1 - i; j){//从小到大排序if (arr[j] arr[j 1]){int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;flag 1;}}if (flag 0){break;}}
}
这段代码中所有变量均为预先确定数量的局部变量 int i、int flag、int j、int temp总计4个整型变量所以空间复杂度是O(1)。
举例2计算空间复杂度
long long* Fibonacci(size_t n)
{if (n 0){return NULL;}long long* fibArray (long long*)malloc((n 1) * sizeof(long long));fibArray[0] 0;fibArray[1] 1;for (int i 2; i n; i){fibArray[i] fibArray[i - 1] fibArray[i - 2];}return fibArray;
}
由于这里动态开辟了n1个额外空间舍去常数后空间复杂度是O(n)
