合肥网站设计网站,什么网站做烘干设备好,设计签名的软件,如何用华为云服务器做网站1、算法效率
衡量一个算法的好坏#xff0c;是从时间和空间两个方面来衡量的#xff0c;换句话说就是从时间复杂度和空间复杂度来衡量的
这里需要补充一点#xff1a;时间复杂度是衡量一个算法的运行快慢#xff0c;空间复杂度是主要衡量一个算法运行所需要的额外空间。 …1、算法效率
衡量一个算法的好坏是从时间和空间两个方面来衡量的换句话说就是从时间复杂度和空间复杂度来衡量的
这里需要补充一点时间复杂度是衡量一个算法的运行快慢空间复杂度是主要衡量一个算法运行所需要的额外空间。
2、时间复杂度
概念算法的事件复杂度是一个函数它定量的描述了该算法的运行时间。一个算法执行所耗费的时间从理论上是不能算出来的所以出现了时间复杂度。一个算法所花费的时间与其中的执行次数成正比例。即算法中的基本操作的执行次数为算法的时间复杂度。
请看下面的代码
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);
}
在实际计算时间复杂度的时候不一定要精确计算出执行次数我们只需要找到其中主导时间复杂度的式子这里需要使用大O的渐进表示法
大O的渐进表示法
1、用常数1取代运行时间中的所有加法常数
2、在修改后的运行次数函数中只保留最高阶项
3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果是大O阶
所以上面的Func1函数的时间复杂度是
还有一种情况是需要注意的当有些算法在不同的情况之下执行的次数不同我们取得是其最坏的情况比如这个算法的执行次数可以是1 N,我们取其最坏的情况所以时间复杂度是O(N)。
下面举一些计算时间复杂度的例子以供大家参考
例1
// 计算Func2的时间复杂度
void Func2(int N)
{int count 0;for (int k 0; k 2 * N ; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}首先进入第一个for循环可见这个for循环要执行2N次然后在进入下面的while循环执行10次一共就是102N次根据上面说的时间复杂度计算方法为O(N)。
例2
// 计算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);
}
这个还是比较容易看出时间复杂度是O(NM)。
例3
// 计算Func4的时间复杂度
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}这个中间的for循环被执行了100次由上述规则可知其时间复杂度是O(1)
例4
// 计算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;}
}
这个是求冒泡排序的时间复杂度我们需要找到最坏的情况在这个最坏的情况这个算法的执行次数为nn-1...1 ,根据上面的时间复杂度的计算方式为O()。
例5
// 计算BinarySearch的时间复杂度
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n - 1;while (begin end){int mid begin ((end - begin) 1);if (a[mid] x)begin mid 1;else if (a[mid] x)end mid;elsereturn mid;}return -1;
}
这个例子是二分法查找每次查找筛选掉一半的数字所以其时间复杂度是O(log n)。
例6
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if(0 N)return 1;return Fac(N-1)*N;
}这个例子中递归了N次所以其时间复杂度是O(N)
例7
// 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if(N 3)return 1;return Fib(N-1) Fib(N-2);
}这个例子递归了次所以时间复杂度是O().
3、空间复杂度
解释这是对一个算法在运行过程中临时占用存储空间大小的量度
需要注意的是空间复杂度是计算的变量的个数这个计算方法也是使用的大O渐进表示法函数运行时所需要的栈空间存储参数、局部变量、一些寄存器的信息等在编译时期已经确定好了因此空间复杂度主要是通过函数在运行的时候显性申请额外的空间来确定。
例1
// 计算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;}
}这个例子使用了常数个额外空间我理解的是没有开辟额外的空间空间复杂度是O(1。
例2
// 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
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;
}
这个开辟了N个空间所以空间复杂度是O(N)
例3
// 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;
}
递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间。空间复杂度为O(N)
