复杂度为o的计算方法

‘壹’ 算法的时间复杂度O（n）到底怎么算

看循环或者递归的层数。

比如该函数为O（n）

intf(intx,inty)
{
inti,j;
for(i=0;i<x;i++)printf("%d
",y);
}

而该函数为O（n2）

intf(intx,inty)
{
inti,j;
for(i=0;i<x;i++)for(j=0;j<y;j++)printf("%d
",y);
}

‘贰’ 归并排序的时间复杂度O是怎么算出来的呢

归并排序每次会把当前的序列一分为二，然后两部分各自排好序之后再合并，这样的话你可以手动模拟出一颗二叉树来，每一层的总计算量是O(n)的，总的层数是O(logn)的，所以总的复杂度是nlogn

‘叁’ 数据结构中算法空间复杂度怎么算

数据结构中算法空间复杂度计算方法：

一个算法的空间复杂度只考虑在运行过程中为局部变量分配的存储空间的大小，它包括为参数表中形参变量分配的存储空间和为在函数体中定义的局部变量分配的存储空间两个部分。

若一个算法为递归算法，其空间复杂度为递归所使用的堆栈空间的大小，它等于一次调用所分配的临时存储空间的大小乘以被调用的次数(即为递归调用的次数加1，这个1表示开始进行的一次非递归调用)。

算法的空间复杂度一般也以数量级的形式给出。如当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)；当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n)；当一个算法的空间复杂度与n成线性比例关系时，可表示为O(n)。若形参为数组，则只需要为它分配一个存储由实参传送来的一个地址指针的空间，即一个机器字长空间；若形参为引用方式，则也只需要为其分配存储一个地址的空间，用它来存储对应实参变量的地址，以便由系统自动引用实参变量。

(3)复杂度为o的计算方法扩展阅读：

空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(n)的空间复杂度了，因为每次递归都要存储返回信息。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。渐近空间复杂度也常常简称为空间复杂度。空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

‘肆’ 数组排序的最少时间复杂度O(nlog2n)怎么计算的

for(int j=1; j<=n; j*=2)

这个循环最终执行的次数假设为x，则x次的时候j=2^x 。

当j>n时停止执行，于是2^x>n ，则可以认为该循环一共执行了log2(n)次。

所以该循环的时间复杂度为o(log2(n))，简记为o(log n) ，忽略掉2的底数。

‘伍’ 如何计算时间复杂度

1、先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））。

2、举例

for（i=1;i<=n;++i）

{for(j=1;j<=n;++j)

{c[ i ][ j ]=0; //该步骤属于基本操作 执行次数：n的平方次

for(k=1;k<=n;++k)

c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数：n的三次方次}}

则有 T（n）= n的平方+n的三次方，根据上面括号里的同数量级，我们可以确定 n的三次方为T（n）的同数量级

则有f（n）= n的三次方，然后根据T（n）/f（n）求极限可得到常数c

则该算法的 时间复杂度：T（n）=O（n的三次方）

),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，

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

关于对其的理解

《数据结构（C语言版）》 ------严蔚敏 吴伟民编着 第15页有句话“整个算法的执行时间与基本操作重复执行的次数成正比。”

基本操作重复执行的次数是问题规模n的某个函数f(n)，于是算法的时间量度可以记为：T(n) = O(f(n))

如果按照这么推断，T(n)应该表示的是算法的时间量度，也就是算法执行的时间。

而该页对“语句频度”也有定义：指的是该语句重复执行的次数。

如果是基本操作所在语句重复执行的次数，那么就该是f(n)。

上边的n都表示的问题规模。

‘陆’ 时间复杂度o(nlogn)的算法是什么

时间复杂度o(nlogn)的算法是采用“分治思想”，将要排序的数组从中间分成前后两个部分，然后对前后两个部分分别进行排序，再将排序好的两部分合并在一起，这样数组就有序。

每次划分区域都选择中间点进行划分，所以递归公式可以写成：T(n) = T(n/2) + T(n/2) + n， T(1) = C(常数) //每次合并都要调用Merge()函数，时间复杂度为O(n)，等价T(n) = 2kT(n/2k) + k * n， 递归的最终状态为T(1)即n/2k = 1，所以k = log2n。

原理分析：

1、运用了分治的思想。选取分区值，将待排序列分为两个前后两部分，前部分数据元素的值小于等于分区值，后部分的数据元素的值大于等于分区值；继续对前后两部分分别进行分区，直到分区大小为1。

2、交换操作的执行次数可以由时间复杂度分析过程得出，Merge()中总的交换次数为n * logn，因为不管两个子序列的大小，子序列中的各个元素都会先放入临时数组temp中，再重新放回原序列；比较操作的次数小于等于交换操作次数，最大交换次数为n * logn。

‘柒’ 算法的时间复杂度O到底怎么算

是说明一个程序根据其数据n的规模大小所使用的大致时间和空间说白了就是表示如果随着n的增长时间或空间会以什么样的方式进行增长例for(inti=0;i