【算法】算法时间复杂度o(1)和o（2）的区别

算法时间复杂度o(1)和o(2)的区别？？？

根据大O定义易知，O（1） = O（2）。用O(1)和O(2)表示同一个函数时，别仅在于常数因子c而已。

【算法】算法时间复杂度o(1)和o（2）的区别

两个都是时间复杂度为常量。复杂度是用来表达算法的复杂程度跟算法输入的规模N的关系。如果不管N是多大，算法的复杂程度都固定是1或者2（比如1条指令，2个循环），那么在“复杂度”这个概念上，两者都一样，叫做“常数阶”复杂度。

O(g(n)) = { f(n) ：存在这样的正常数c和n0，使得对任意的n >= n0， 有0 <= f(n) <= cg(n)成立 }，则g(n)是f(n)的渐进上界。O（g(n)）是指所有与g(n)具有相同增长率或比其增长率小的函数的。

扩展资料：

常见的时间复杂度：

按数量级递增排列，常见的时间复杂度有：

常数阶O(1)；对数阶复杂度，即O(log2n)，比如有序数组的二分查找；线性阶O(n)，比如链式表的随机访问；线性对数阶O(nlogn)，比如某些排序算法；平方阶O(n^2)，立方阶O(n^3)等等。有些算法特别复杂，复杂度可能是O(n!)，O(n^n)等等。

k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

参考资料来源：

时间复杂度是一个函数，它定量描述了该算法的运行时间。常见的时间复杂度有以下几种。

1，log(2)n，n，n log(2)n ，n的平方，n的三次方，2的n次方，n!

1指的是常数。即，无论算法的输入n是多大，都不会影响到算法的运行时间。这种是的算法。而n！（阶乘）是非常的算法。当n变大时，算法所需的时间是不可接受的。

用通俗的话来描述，我们假设n=1所需的时间为1秒。那么当n = 10，000时。

O（1）的算法需要1秒执行完毕。

O（n）的算法需要10，000秒 ≈ 2.7小时 执行完毕。

O（n2）的算法需要100，000，000秒 ≈ 3.17年 执行完毕。

O（n！）的算法需要XXXXXXXX(系统的计算器已经算不出来了)。

可见算法的时间复杂度影响有多大。

所以O（1）和O（n）了2.7小时，区别显而易见。

没有O(2)这一说，要么是O(1)，要么是O(f(N))

O(1)与O(2)的阶位一样，所以仅仅是常数区别

为什么说算法时间复杂度是为对数阶、幂函数阶时，算法的运行时间是可以接受的，称这些算法

因为随着数据量的增加，对数阶，幂函数阶的算法时间开销增加速度逐渐减小，而指数阶阶乘阶消耗时间增加速度太快，但数据量达到一定程度的时候，前者消耗的时间依然在可接受范围内，而后者将超出可接受时间。

比如 log n 和n^3 当n=10^9时 一般的电脑按照每秒计算10^9次 。那么n^3的算法已经要消耗数万年的时间才能解决，而log n的算法只需要不到1s就能够出算法

求该阶乘算法的时间复杂度：int Factorial(int n)if(n==0) return 1；else return n Factorial(n-1)；

#include"stdio.h"intprime(intn){if(n>1)returnnprime(n-1);elsereturn1;}intmain(){into;for(o=1;o<=10;o++)printf("%d!=%d",o,prime(o));}

int f(int n){ if(n==1)return 1; else return (nf(n-1)); }这个函数有什么作用？时间复杂度是？

这个函数是用来求阶乘的，用了递归方法。输入100，就会得到100的阶乘。但是由于数值太大，会导致溢出。建议将返回值类型改为 double 型。

计算N的阶乘需要进行N次乘法运算，因此时间复杂度为O(N)。

由递归方式求的N的阶乘（即N，），时间复杂度是多少

每次递归内部计算时间是常数，故O（n）。

用递归方法计算阶乘，函数表达式为f(n)=1 若n=0 f(n)=nf(n-1)，若n>0，如果n=0，就调用1次阶乘函数，如果n=1，就调用2次阶乘函数，如果n=2，就调用3次阶乘函数，如果n=3，就调用4次阶乘函数。

扩展资料：

注意事项：

利用递归树方法求算法复杂度，其实是提供了一个好的猜测，简单而直观。在递归树中每一个结点表示一个单一问题的代价，子问题对应某次递归函数调用，将树中每层中的代价求和，得到每层代价，然后将所有层的代价求和，得到所有层次的递归调用总代价。

递归树适合用来生成好的猜测，然后可用代入法来验证猜测是否正确。当使用递归树来生成好的猜测时，常常要忍受一点儿不精确，因为关注的是如何寻找解的一个上界。

参考资料来源：

参考资料来源：

参考资料来源：