大兴安岭建设局网站,使用net域名的大网站,网站建站公司模板,多语网站1.算法效率
1.1 如何衡量一个算法的好坏#xff1f;
比方说我们非常熟悉的斐波拉契数列#xff1a;
long long Fib(int N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}
递归实现方式非常简洁#xff0c;但一定好吗#xff1f;如何衡量其好与坏#xff1f;
1…1.算法效率
1.1 如何衡量一个算法的好坏
比方说我们非常熟悉的斐波拉契数列
long long Fib(int N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}
递归实现方式非常简洁但一定好吗如何衡量其好与坏
1.2算法的复杂度
定义 算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源 。因此 衡量一个算法的好坏一般 是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算 机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计 算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 1.3复杂度对于校招的重要性
2.时间复杂度
定义 在计算机科学中 算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一 个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例 算法中的基本操作的执行次数为算法的时间复杂度。 就是找到某条基本语句与问题规模N之间的数学表达式就是算出了该算法的时间复杂度 2.大O的渐进表示法规则 时间复杂度和空间复杂度一般都使用大O的渐进表示法进行表示大O的渐进表示法规则如下 1、所有常数都用常数1表示。 2、只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项的系数得到的结果就是大O阶。 我们就以开头所提及的递归得到斐波拉契数列的代码为例子如果我们传递了一个参数n即我们要求fn的值那么应该运行多少次如f(n)f(n-1)f(n-2)而f(n-1)f(n-2)f(n-3) f(n-2)f(n-3)f(n-4)... 因为右下角的递归函数会提前结束所以图中三角形必定有一块是没有数据的但是当N趋于无穷时那缺省的一小块便可以忽略不计这时总共调用斐波那契函数的次数为 再有等比数列求和得出2N - 1。 那么用大O渐进表示法表示该函数的时间复杂度为O(2N) 。 注意 递归算法的时间复杂度 递归的次数 * 每次递归函数中的次数。 再举一个列子 //计算Func1的时间复杂度
void Func1(int N)
{int count 0;for (int i 0; i 2 * N; i){for (int j 0; j 2 * N; j){count;}}for (int k 0; k 2 * N; k){count;}
}该函数执行了一个嵌套循环共执行了4 * pown,2)次又单执行一个for循环共执行2*N次 那么时间复杂度为4*pown,2)2*n 次用大O渐进表示法:O(pown2 例2 //计算Func2的时间复杂度
void Func2(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}该函数内部执行了一个for循环共100次Func2函数内语句的执行次数不会随着传入的变量N的改变而改变即执行的次数为常数次。Func2函数的时间复杂度为T(N) 100 。 由大O渐进表示法所有的常数都用1来表示即O(1); 空间复杂度 空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。空间复杂度不是程序占用了多少字节的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。 例1 //计算冒泡排序函数的空间复杂度
void BubbleSort(int* a, int N)
{assert(a);for (int i 0; i N; i){int exchange 0;for (int j 0; j N - 1 - i; j){if (a[j]a[j 1]){int tmp a[j];a[j] a[j 1];a[j 1] tmp;exchange 1;}}if (exchange 0)break;}
}例2 //计算阶乘递归函数的空间复杂度
long long Factorial(int N)
{return N 2 ? N : Factorial(N - 1)*N;
}阶乘递归函数会依次调用Factorial(N),Factorial(N-1),…,Factorial(2),Factorial(1)开辟了N个空间所以空间复杂度为O(N) 。同理我们开头所提到的斐波拉契函数也是ON。 注递归算法的空间复杂度通常是递归的深度即递归多少层。 感谢你的阅读下次再见。
