算法中ifelse和三目运算的时间复杂度是多少？

if语句中含有for循环语句的算法复杂度分析

//其实理解了 很简单.

算法中ifelse和三目运算的时间复杂度是多少？

//就是如果击中,就开始执行下面的代码

lings(b);

for(k=0;k<48;k++){

if(a[r][c][k]==1){//如果a[r][c][k]==1就执行下步代码

type++;

for(i=0;i<7;i++){

for(j=0;j<7;j++){

b[i][j]=b[i][j]+a[i][j][k];

}}

}//这段代码,反之 else就是相当于a[r][c][k]!=1,就执行ling(a,k);

//如果不击中,就开始执行下面的代码

lings(b);

for(k=0;k<48;k++){

flag=pan2(a,k);

if(flag!=0){ //此处又有个判断如果flag变量的值!=0

if(a[r][c][k]!=1)//如果a[r][c][k]==1就执行下步代码

{type++;

for(i=0;i<7;i++){

for(j=0;j<7;j++){

b[i][j]=b[i][j]+a[i][j][k];

}}

}else//反之 else就是相当于a[r][c][k]!=1下面的那部分带

ling(a,k);

表示我表达能力不强 所以只能做到这一步 了

JAVA中if else 和 三目运算 的时间复杂度 各是多少

有人做过测试

三目运算的效率是if

else的1.09倍左右，

至于为什么会快，个人觉得是因为if else 在执行过程中两条语句，三目运算符 是一条语句

时间复杂度

求解算法的时间复杂度的具体步骤是：

⑴ 找出算法中的基本语句；

算法中执行次数多的那条语句就是基本语句，通常是内层循环的循环体。

⑵ 计算基本语句的执行次数的数量级；

只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的次幂正确即可，可以忽略所有低次幂和次幂的系数。这样能够简化算法分析，并且使注意力集中在重要的一点上：增长率。

⑶ 用大Ο记号表示算法的时间性能。

将基本语句执行次数的数量级放入大Ο记号中。

果算法中包含嵌套的循环，则基本语句通常是内层的循环体，如果算法中包含并列的循环，则将并列循环的时间复杂度相加。例如：

个for循环的时间复杂度为Ο(n)，第二个for循环的时间复杂度为Ο(n2)，则整个算法的时间复杂度为Ο(n+n2)=Ο(n2)。

Ο(1)表示基本语句的执行次数是一个常数，一般来说，只要算法中不存在循环语句，其时间复杂度就是Ο(1)。

其中Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)称为多项式时间，而Ο(2n)和Ο(n!)称为指数时间。计算机科学家普遍认为前者（即多项式时间复杂度的算法）是有效算法，把这类问题称为P（Polynomial,多项式）类问题，而把后者（即指数时间复杂度的算法）称为NP（Non-Deterministic Polynomial, 非确定多项式）问题。

一般来说多项式级的复杂度是可以接受的，很多问题都有多项式级的解——也就是说，这样的问题，对于一个规模是n的输入，在n^k的时间内得到结果，称为P问题。有些问题要复杂些，没有多项式时间的解，但是可以在多项式时间里验证某个猜测是不是正确。

4）在计算算法时间复杂度时有以下几个简单的程序分析法则:

(1).对于一些简单的输入输出语句或赋值语句,近似认为需要O(1)时间

(2).对于顺序结构,需要依次执行一系列语句所用的时间可采用大O下"求和法则"

求和法则:是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1(n)+T2(n)=O(max(f(n), g(n)))

特别地,若T1(m)=O(f(m)), T2(n)=O(g(n)),则 T1(m)+T2(n)=O(f(m) + g(n))

(3).对于选择结构,如if语句,它的主要时间耗费是在执行then字句或else字句所用的时间,需注意的是检验条件也需要O(1)时间

(4).对于循环结构,循环语句的运行时间主要体现在多次迭代中执行循环体以及检验循环条件的时间耗费,一般可用大O下"乘法法则"

乘法法则: 是指若算法的2个部分时间复杂度分别为 T1(n)=O(f(n))和 T2(n)=O(g(n)),则 T1 T2=O(f(n) g(n))

(5).对于复杂的算法,可以将它分成几个容易估算的部分,然后利用求和法则和乘法法则技术整个算法的时间复杂度

另外还有以下2个运算法则:(1) 若g(n)=O(f(n)),则O(f(n))+ O(g(n))= O(f(n))；(2) O(Cf(n)) = O(f(n)),其中C是一个正常数

简单的说 就是可以将两个算法的时间复杂度 相加或相乘

(1)、O(1)

以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。

(2)、O(n2)

2.1. 交换i和j的内容

解：因为Θ(2n2+n+1)=n2（Θ即：去低阶项，去掉常数项，去掉高阶项的常参得到），所以T(n)= =O(n2)；

去低阶项，去掉常数项，去掉高阶项的常参得到

该算法的时间复杂度T(n)=O(n^2).

(3)、O(n)

T(n)=2+n+3(n-1)=4n-1=O(n).

该算法程序的时间复杂度为 O(n)

后续更新

时间复杂度怎么算

简单理解，时间复杂度就是执行语句被调用了多少次。 (1)如果只调用了一次，如： x=5; if(x<-4) {x=x+4;} else {x=x+3;} 在大括号中的内容，只会调用一个语句，那么O(n)=1; (2)如果调用了两次，如： x=5; if(x<-4) {x=x+4;} else {x=x+3;} x=x+56; 在大括号中的内容，只会调用一个语句，但是在，还有一个计算公式要调用语句；总共加起来就是调用2次。那么O(n)=2; （3）用1个FOR循环调用 for(x=0;x

时间复杂度怎么算例题

时间复杂度算例题如下：

(1) 递归执行过程

例子：求N!。

这是一个简单的"累乘"问题，用递归算法也能解决。

n! = n (n - 1)! n > 1

0! = 1, 1! = 1 n = 0,1

因此，递归算法如下：

Ja代码

fact(int n) {

if(n == 0 || n == 1)

return 1;

else

return n fact(n - 1);

}以n=3为例，看运行过程如下：

fact(3) ----- fact(2) ----- fact(1) ------ fact(2) -----fact(3)

递归 回溯

递归算法在运行中不断调用自身降低规模的过程，当规模降为1，即递归到fact(1)时，满足停止条件停止递归，开始回溯(返回调用算法)并计算，从fact(1)=1计算返回到fact(2);计算2fact(1)=2返回到fact(3)；计算3fact(2)=6，结束递归。

算法的起始模块也是终止模块。

(2) 递归实现机制

每一次递归调用，都用一个特殊的数据结构"栈"记录当前算法的执行状态，特别地设置地址栈，用来记录当前算法的执行位置，以备回溯时正常返回。递归模块的形式参数是普通变量，每次递归调用得到的值都是不同的，他们也是由"栈"来存储。

(3) 递归调用的几种形式

一般递归调用有以下几种形式(其中a1、a2、b1、b2、k1、k2为常数)。

<1> 直接简单递归调用： f(n) {...a1 f((n - k1) / b1); ...};

<2> 直接复杂递归调用： f(n) {...a1 f((n - k1) / b1); a2 f((n - k2) / b2); ...};

<3> 间接递归调用： f(n) {...a1 f((n - k1) / b1); ...}，

g(n) {...a2 f((n - k2) / b2); ...}。

2. 递归算法效率分析方法

递归算法的分析方法比较多，常用的便是迭代法。

迭代法的基本步骤是先将递归算法简化为对应的递归方程，然后通过反复迭代，将递归方程的右端变换成一个级数，求级数的和，再估计和的渐进阶。

<1> 例：n!

算法的递归方程为： T(n) = T(n - 1) + O(1);

迭代展开： T(n) = T(n - 1) + O(1)

= T(n - 2) + O(1) + O(1)

= T(n - 3) + O(1) + O(1) + O(1)

= ......

= O(1) + ... + O(1) + O(1) + O(1)

= n O(1)

= O(n)

这个例子的时间复杂性是线性的。

<2> 例：如下递归方程：

T(n) = 2T(n/2) + 2, 且假设n=2的k次方。

T(n) = 2T(n/2) + 2

= 2(2T(n/22) + 2) + 2

= 4T(n/22) + 4 + 2

= 4(2T(n/222) + 2) + 4 + 2

= 222T(n/222) + 8 + 4 + 2

= ...

= 2的(k-1)次方 T(n/2的(i-1)次方) + $(i:1~(k-1))2的i次方

= 2的(k-1)次方 + (2的k次方) - 2

= (3/2) (2的k次方) - 2

= (3/2) n - 2

= O(n)

这个例子的时间复杂性也是线性的。

<3> 例：如下递归方程：

T(n) = 2T(n/2) + O(n), 且假设n=2的k次方。

T(n) = 2T(n/2) + O(n)

= 2T(n/4) + 2O(n/2) + O(n)

= ...

= O(n) + O(n) + ... + O(n) + O(n) + O(n)

= k O(n)

= O(kn)

= O(nlog2n) //以2为底

一般地，当递归方程为T(n) = aT(n/c) + O(n), T(n)的解为：

O(n) (a1)

O(nlog2n) (a=c && c>1) //以2为底

O(nlogca) (a>c && c>1) //n的(logca)次方，以c为底

上面介绍的3种递归调用形式，比较常用的是种情况，第二种形式也有时出现，而第三种形式(间接递归调用)使用的较少，且算法分析

比较复杂。 下面举个第二种形式的递归调用例子。

<4> 递归方程为：T(n) = T(n/3) + T(2n/3) + n

为了更好的理解，先画出递归过程相应的递归树：

n --------> n

n/3 2n/3 --------> n

n/9 2n/9 2n/9 4n/9 --------> n

...... ...... ...... ....... ......

--------

总共O(nlogn)

累计递归树各层的非递归项的值，每一层和都等于n，从根到叶的长路径是：

n --> (2/3)n --> (4/9)n --> (12/27)n --> ... --> 1

设长路径为k，则应该有：

(2/3)的k次方 n = 1

得到 k = log(2/3)n // 以(2/3)为底

于是 T(n) <= (K + 1) n = n (log(2/3)n + 1)

即 T(n) = O(nlogn)

由此例子表明，对于第二种递归形式调用，借助于递归树，用迭代法进行算法分析是简单易行的。