C语言写程序时 出现的时间复杂度 具体是什么意思？

Python011

C语言写程序时 出现的时间复杂度 具体是什么意思？,第1张

这东西详细手打有点，去帮你找了个讲的比较详细的。

哪不懂可以追问

简单理解，时间复杂度就是执行语句被调用了多少次。

(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=0x<nx++)

{x=x+1}

x会从0到n-1循环，执行的语句就是将当前x值加入新的x中，总共调用n次；那么O(n)=n

(4）用2个嵌套FOR循环调用

for(x=0x<nx++)

{

for(y=1y<=ny++)

{x=x+y}

}

遇到嵌套循环，可以先将外面的FOR语句中的变量固定为初始值x=0，主要看里面的FOR语句的时间复杂度，很明显，里面语句执行次数是从1到n总共调用n次，O(n)=n；这还只是x=0时的调用。x可以从0到n-1，共n次。每次调用都会执行n次调用y的情况，因此，执行语句x=x+y；总共会调用n*n次。O(n)=n^2。

数执行语句的执行次数，就是时间复杂度。注意：

(1)找到正确的执行语句。

(2)for循环中的初始值和终止值。

for(i=0i<ni++)

i值变化是从0到n-1，共n次。

for(i=0i<=ni++)

i值变化是从0到n，共n+1次。

(3)注意for循环的调用顺序，从里面到外面进行的。

(1)两层循环，每层执行n次，时间复杂度为O(n^2)

(2)也是两层循环，可以算出总共执行了多少次，其中n的最高次数为2，所以时间复杂度也为O(n^2)

(3)同上，O(n^2)

(4)循环体执行次数为n-1，时间复杂度为O(n)

(5)三层循环，每层执行n次，时间复杂度为O(n^3)

数据结构课程中，对算法进行评估要求不是很高，只需大致算出语句执行了多少次即可，常见的、能写成小段代码考察的一般都是O(n^2)、O(n)、O(n^3)，O(log N)的就那么几个，记住就行。