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

看循环或者递归的层数。

比如该函数为O（n）

int f(int x,int y)
{
int i,j;
for(i=0;i<x;i++)printf("%d\n",y);
}

而该函数为O（n2）

int f(int x,int y)
{
int i,j;
for(i=0;i<x;i++)for(j=0;j<y;j++)printf("%d\n",y);
}

你上下好像是两个独立的函数，那就分开算：

第一个计算从2到n的平方根，有没有n的因子，有返回0，没有返回1，应该是一个判断n是否是质数的函数，那么它的复杂度是动态的，最好的可能是能被2除，则复杂度为1，最差的情况是n是质数，则复杂度为n的平方根-1，可以简单记为O(n的开方)

第二个，可能有些语法错误：

p是什么，全局变量？因为涉及pj所以p的初值很关键

第二个for循环把i重置为1和j相同，所以导致此for循环不会执行，那么整体的复杂度就是第一重循环即O(n)

如果做如下改动：

long sun(int n)
{ 
    int s = 0, p = 0;
  
    for(i = 1; i <= n; i++) 
    {
        p = 1; 
        for(j = 1; j <= i; j++)
            p = p  j;
        s += p;
    }
  
    return s;
}

那这个程序就变成了求1到n所有数的阶乘的和，那么它的复杂度为：

一重for循环，执行了n次

二重for循环，执行的次数相当于一个从1到n的等差数列的和，为(n+1)n/2，即n^2/2 + n/2

当n趋近无穷时，可以忽略低次幂和系数，即其复杂度为O(n^2)

算法的复杂性
算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。
计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。
不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
简言之，在算法学习过程中，我们必须首先学会对算法的分析，以确定或判断算法的优劣。
1时间复杂性：
例1：设一程序段如下（为讨论方便，每行前加一行号）
(1) for i:=1 to n do
(2) for j:=1 to n do
(3) x:=x+1

试问在程序运行中各步执行的次数各为多少？
解答：
行号 次数(频度)
(1) n+1
(2) n(n+1)
(3) nn
可见，这段程序总的执行次数是：f(n)=2n2+2n+1。在这里，n可以表示问题的规模，当n趋向无穷大时，如果 f(n)的值很小，则算法优。作为初学者，我们可以用f(n)的数量级O来粗略地判断算法的时间复杂性，如上例中的时间复杂性可粗略地表示为T(n)=O(n2)。
2空间复杂性:
例2:将一一维数组的数据(n个)逆序存放到原数组中,下面是实现该问题的两种算法:
算法1:for i:=1 to n do
b[i]:=a[n-i+1];
for i:=1 to n do
a[i]:=b[i];
算法2:for i:=1 to n div 2 do
begin
t:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t
end;
算法1的时间复杂度为2n,空间复杂度为2n
算法2的时间复杂度为3n/2,空间复杂度为n+1
显然算法2比算法1优，这两种算法的空间复杂度可粗略地表示为S(n)=O(n)
信息学比赛中，经常是：只要不超过内存，尽可能用空间换时间。

关于时间复杂度的计算是按照运算次数来进行的，比如1题：
sum1(intn)
{intp=1,sum=0,m;//1次
for(m=1;m<=n;m++)//n+1次
{p=m;//n次
sum+=p;}//n次
return(sum);//1次
}
最后总的次数为
1+（n+1）+n+n+1+1=3n+3
所以时间复杂度f（o）=n；（时间复杂度只管n的最高次方，不管他的系数和表达式中的常量）
其余的一样，不明白的可以来问我

1 一般情况下，算法的基本 *** 作重复执行的次数是模块n的某一个函数f（n），因此，算法的时间复杂度记做：T（n）=O（f（n））分析：随着模块n的增大，算法执行的时间的增长率和f（n）的增长率成正比，所以f（n）越小，算法的时间复杂度越低，算法的效率越高。2 在计算时间复杂度的时候，先找出算法的基本 *** 作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））例：算法：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的三次方）3分类按数量级递增排列，常见的时间复杂度有：常数阶O(1),对数阶O(log2n),线性阶O(n), 线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),，k次方阶O(nk), 指数阶O(2n) 。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

时间复杂度计算

学习数据结构时，觉得时间复杂度计算很复杂，怎么也看不懂，差不多三年之后，还是不懂，马上就要找工作了，赶紧恶补一下吧：

首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n 的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。

当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。

此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。

常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k 次方阶O(n^k)、指数阶O(2^n)。

1 大O 表示法

定义

设一个程序的时间复杂度用一个函数 T(n) 来表示，对于一个查找算法，如下：

int seqsearch( int a[], const int n, const int x)

{

int i = 0;

for (; a[i] != x && i

if ( i == n) return -1;

else return i;

}

这个程序是将输入的数值顺序地与数组中地元素逐个比较，找出与之相等地元素。

在第一个元素就找到需要比较一次，在第二个元素找到需要比较2次，„„ ，在第n 个元素找到需要比较n 次。对于有n 个元素的数组，如果每个元素被找到的概率相等，那么查找成功的平均比较次数为:

f(n) = 1/n (n + (n-1) + (n-2) + + 1) = (n+1)/2 = O(n)

这就是传说中的大O 函数的原始定义。

用大O 来表述

要全面分析一个算法，需要考虑算法在最坏和最好的情况下的时间代价，和在平均情况下的时间代价。对于最坏情况，采用大O 表示法的一般提法（注意，这里用的是“一般提法”）是：当且仅当存在正整数c 和n0, 使得 T(n) = n0 都成立。则称该算法的渐进时间复杂度为T(n) = O(f(n))。这个应该是高等数学里面的第一章极限里面的知识。这里f(n) = (n+1)/2, 那么c f(n)也就是一个一次函数。就是在图象上看就是如果这个函数在cf(n)的下面，就是复杂度为T(n) = O(f(n))。

对于对数级，我们用大O 记法记为O(log2N)就可以了。

规则

1） 加法规则

T(n,m) = T1(n) + T2(n) = O ( max (f(n), g(m) )

2) 乘法规则

T(n,m) = T1(n) T2(m) = O (f(n) g(m))

3) 一个特例

在大O 表示法里面有一个特例，如果T1(n) ＝ O， c是一个与n 无关的任意常数，T2(n) = O ( f(n) ) 则有

T(n) = T1(n) T2(n) = O ( cf(n) ) = O( f(n) )

也就是说，在大O 表示法中，任何非0正常数都属于同一数量级，记为O(1)。

4) 一个经验规则

有如下复杂度关系

c

其中c 是一个常量，如果一个算法的复杂度为c 、 log2N 、n 、 nlog2N , 那么这个算法时间效率比较高 ，如果是 2^n , 3^n ,n!, 那么稍微大一些的n 就会令这个算法不能动了，居于中间的几个则差强人意

1）基本知识点：没有循环的一段程序的复杂度是常数，一层循环的复杂度是O(n),两层循环的复杂度是O(n^2) （我用^2表示平方，同理 ^3表示立方）；

2）二维矩阵的标准差，残差，信息熵，fft2,dwt2,dct2的时间复杂度: 标准差和残差可能O(n)，FFT2是O(nlog(n))，DWT2可能也是O(nlog(n))；信息熵要求概率，而dct 的过程和jpeg 一样。因为和jpeg 一样, 对二难矩阵处理了Y=TXT"，Z=YMask，这样子, 还有分成88子图像了;

3)example ：

1、设三个函数f,g,h 分别为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^15+5000nlgn

请判断下列关系是否成立：

（1） f(n)=O(g(n))

（2） g(n)=O(f(n))

（3） h(n)=O(n^15)

（4） h(n)=O(nlgn)

这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n))，这里的"O" 是数学符号，它的严格定义是" 若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C 和n0 ,使得当n≥n0时都满足

0≤T(n)≤Cf(n)。" 用容易理解的话说就是这两个函数当整型自变量n 趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。

◆ (1)成立。题中由于两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。

◆ （2）成立。与上同理。

◆ （3）成立。与上同理。

◆ （4）不成立。由于当n→∞时n^15比nlgn 递增的快，所以h(n)与nlgn 的比值不是常数，故不成立。

2、设n 为正整数，利用大"O" 记号，将下列程序段的执行时间表示为n 的函数。

(1) i=1; k=0

while(i

{ k=k+10i;i++;

}

解答：T(n)=n-1， T(n)=O(n)， 这个函数是按线性阶递增的。

(2) x=n; // n>1

while (x>=(y+1)(y+1))

y++;

解答：T(n)=n1/2 ，T(n)=O(n1/2)，最坏的情况是y=0，那么循环的次数是n1/2

次，这是一个按平方根阶递增的函数。

(3) x=91; y=100;

while(y>0)

if(x>100)

{x=x-10;y--;}

else x++;

解答： T(n)=O(1)，这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n 没有 没。这段程序的运行是和n 无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。

同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

1、时间复杂度

（1）时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

（2）时间复杂度

在刚才提到的时间频度中，n 称为问题的规模，当n 不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。

一般情况下，算法中基本 *** 作重复执行的次数是问题规模n 的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n 趋近于无穷大时，T （n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。

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

常数阶O(1),对数阶O(log2n),线性阶O(n),

线性对数阶O(nlog2n),平方阶O(n2)，立方阶O(n3),，

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

2、空间复杂度

与时间复杂度类似，空间复杂度是指算法在计算机内执行时所需存储空间的度量。记作:

S(n)=O(f(n))

我们一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再赘述。

（3）渐进时间复杂度评价算法时间性能

主要用算法时间复杂度的数量级(即算法的渐近时间复杂度) 评价一个算法的时间性能。

例3．7有两个算法A1和A2求解同一问题，时间复杂度分别是

T1(n)=100n2，T2(n)=5n3。

（1）当输入量n ＜20时，有T1(n)＞T2(n)，后者花费的时间较少。

（2）随着问题规模n 的增大，两个算法的时间开销之比5n3/100n2=n/20亦随着增大。即当问题规模较大时，算法A1比算法A2要有效地多。 它们的渐近时间复杂度O(n2)和O(n3)从宏观上评价了这两个算法在时间方面的质量。在算法分析时，往往对算法的时间复杂度和渐近时间复杂度不予区分，而经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。

例3．8算法MatrixMultiply 的时间复杂度一般为T(n)=O(n3)，f(n)=n3是该算法中语句(5)的频度。下面再举例说明如何求算法的时间复杂度。

例3．9交换i 和j 的内容。

Temp=i;

i=j;

j=temp;

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n 无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。

如果算法的执行时间不随着问题规模n 的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

例3．10变量计数之一。

(1) x=0;y=0;

(2) for(k-1;k

(3) x++;

(4) for(i=1;i

(5) for(j=1;j

(6) y++;

一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n2，所以该程序段的时间复杂度为T(n)=O(n2)。

当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

例3．11变量计数之二。

(1) x=1;

(2) for(i=1;i

(3) for(j=1;j

(4) for(k=1;k

(5) x++;

该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n 没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n 有关，因此可以从内层循环向外层分析语句(5)的执行次数：

则该程序段的时间复杂度为T(n)=O(n3/6+低次项)=O(n3)。

（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。

例3．12在数值A[0n-1]中查找给定值K 的算法大致如下：

(1)i=n-1;

(2)while(i>=0&&(A[i]!=k))

(3) i--;

(4)return i;

此算法中的语句(3)的频度不仅与问题规模n 有关，还与输入实例中A 的各元素取值及K 的取值有关:

①若A 中没有与K 相等的元素，则语句(3)的频度f(n)=n；

②若A 的最后一个元素等于K, 则语句(3)的频度f(n)是常数0。

（5）最坏时间复杂度和平均时间复杂度

最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度。

这样做的原因是：最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界，这就保证了算法的运行时间不会比任何更长。

例3．19查找算法例1·8在最坏情况下的时间复杂度为T(n)=0(n)，它表示对于任何输入实例, 该算法的运行时间不可能大于0(n)。

平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。

常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、„、k 次方阶0(nk)、指数阶0(2n)。显然，时间复杂度为指数阶0(2n)的算法效率极低，当n 值稍大时就无法应用。

类似于时间复杂度的讨论，一个算法的空间复杂度(Space

Complexity)S(n)定义为该算法所耗费的存储空间，它也是问题规模n 的函数。渐近空间复杂度也常常简称为空间复杂度。算法的时间复杂度和空间复杂度合称为算法的复杂度。

---