手机微网站 模板,建筑企业资质查询官方网站,湖南智能网站建设费用,备案期间 需要关闭网站当我们面对一个问题时#xff0c;会有许多种解题思路。我们现在的计算机技术已经达到非常先进的地步#xff0c;所以当我们用不同的方法对待问题时#xff0c;时间差异不会很明显#xff0c;内存差异我们一般在平常小问题时感受不到#xff0c;所以我们不会去纠结程序的优…当我们面对一个问题时会有许多种解题思路。我们现在的计算机技术已经达到非常先进的地步所以当我们用不同的方法对待问题时时间差异不会很明显内存差异我们一般在平常小问题时感受不到所以我们不会去纠结程序的优化过程。
但是在以后的生活中程序内容将会非常丰富时间与空间的效率也就能体现出来今天就让我们对程序的时间与空间进行学习。
目录
算法效率 如何衡量一个算法的好坏
算法的复杂度 时间复杂度
时间复杂度的概念
大O的渐进表示法
常见时间复杂度计算举例
空间复杂度
常见空间复杂度计算举例
常见复杂度对比 算法效率 如何衡量一个算法的好坏 如何衡量一个算法的好坏呢比如对于以下斐波那契数列 long long Fib(int N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}斐波那契数列的递归实现方式非常简洁但简洁一定好吗那该如何衡量其好与坏呢 虽然代码非常简洁但是当我们将N的取值大于50之后想要算出结果就非常的困难电脑会进行大量计算。 算法的复杂度
算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏一般 是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计 算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 时间复杂度
时间复杂度的概念
时间复杂度的定义在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一 个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知 道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法 的时间复杂度。
即找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度。
我们通过一个程序进一步了解时间复杂度
// 请计算一下Func1中count语句总共执行了多少次
void Func1(int N)
{
int count 0;
for (int i 0; i N ; i)
{for (int j 0; j N ; j){count;}
}for (int k 0; k 2 * N ; k)
{count;
}
int M 10;
while (M--)
{count;
}
printf(%d\n, count);
}我们需要计算出count总共执行了多少次在for循环嵌套中count使用了N²次在第三个for循环中又执行了2N次最后在while循环中M10所以count循环了10次所以count总共执行了N²2N10次 当我们在N取大值时表达式中只有最高次数项对表达式影响大。
实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。
大O的渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号。 推导大O阶方法 1、用常数1取代运行时间中的所有加法常数。 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。 使用大O的渐进表示法以后Func1的时间复杂度为O(N²) ;
N 10 F(N) 100 N 100 F(N) 10000 N 1000 F(N) 1000000
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。 另外有些算法的时间复杂度存在最好、平均和最坏情况 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界) 例如在一个长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到 在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N) 常见时间复杂度计算举例
// 计算Func3的时间复杂度
void Func3(int N, int M)
{int count 0;for (int k 0; k M; k){count;}for (int k 0; k N ; k){count;}printf(%d\n, count);
}这段程序在第一个for循环中执行了M次在第二个for循环中执行了N次所以用大O表示O(MN)
// 计算BubbleSort的时间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if (exchange 0)break;}
}求BubbleSort的时间复杂度。这个函数就是冒泡排序法如果我们对一组数组进行排序最好的情况是N只需要检查一次即可。最坏的情况就是一直要进行顺序调换需要执行(N*(N1))/2次通过推导大O阶方法时间复杂度一般看最 坏时间复杂度为 O(N^2)。
// 计算BinarySearch的时间复杂度
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n-1;// [begin, end]begin和end是左闭右闭区间因此有号while (begin end){int mid begin ((end-begin)1);if (a[mid] x)begin mid1;else if (a[mid] x)end mid-1;elsereturn mid;}return -1;
}这个函数是二分查找法我们需要求此函数的时间复杂度。 根据上图我们就可以得出二分查找的时间复杂度为O(logN).
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}我们现在已经学会了时间复杂度我们可以算一下用递归求斐波那契数列的时间复杂度我们就能知道为什么用递归求斐波那契数列只是代码简洁但并不是好方法 通过上图我们就可以得到这个递归的时间复杂度为O(2^N)所以这个算法很不好
空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。
空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。 空间复杂度计算规则基本跟实践复杂度类似也使用大O渐进表示法。
注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因 此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
常见空间复杂度计算举例
// 计算BubbleSort的空间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i-1] a[i]){Swap(a[i-1], a[i]);exchange 1;}}if (exchange 0)break;}
}此函数使用了常数个额外空间开辟了size_t int、int exchange、size_t i这三个变量空间所以空间复杂度为 O(1)。
// 计算斐波那契递归Fib的空间复杂度
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}使用递归计算斐波那契数因为在每次调用函数时都要开辟一块函数栈帧当调用完成后就会对此函数的栈帧空间进行销毁所以当我们计算空间复杂度时我们得按着顺序进行累加计算当函数还没有使用完成时不会去递归调用别的内容。因为斐波那契额数递归如同一个树但是空间复杂度与时间复杂度不相同空间复杂度是看在同一时间调用的次数所以这个函数的空间复杂度为N用大O表示为O(N).
常见复杂度对比 所以复杂度对一个程序有很大的影响当我们在设计程序时不妨先停下来好好想一想怎样设计才是最优解呢
