数据结构-算法时间复杂度

预备知识

时间复杂度

时间复杂度，又称"渐进式时间复杂度"，表示代码执行时间与数据规模之间的增长关系。
核心:

• 只关注循环执行次数最多的那段代码
• 加法法则（总复杂度等于量级最大的那段代码的复杂度）
• 乘法法则（嵌套代码复杂度等于内外代码复杂度的乘积）

空间复杂度

空间复杂度，也称渐进空间复杂度，表示代码存储空间与数据规模之间的增长关系。
与时间复杂度类似, 主要看程序申请的空间大小

任务

// (1)
for(sum = 0,i=0 ;i<N; i++ )
sum++;

// (2)
for(i = 0,sum= 0;|i< N ; i++ )
for(j = 0; j< N ;j++)
sum++;

// (3)
sum = 0;
for(i=0;i<N; i++ )
for(j = 0; j< N*N ;j++)
sum++;

// (4)
sum = 0;
for(i=0;i<N; i++ )
for(j = 0; j< N ;j++)
for(k = 0; k< N ;k++)
sum++ ;

// (5)
sum = 0;
for(i=0;i<N;i=i*2 )n
sum++;

解答

(1)

for(sum=0,i=0;i < N;i++) 循环次数N
大O: O(n)

(2)

for(i=0,sum=0;i<N;i++) 循环次数N
for(j=0;j<N;j++) 循环次数N
大O: O(n^2)

(3)

for(i=0,sum=0;i < N;i++) 循环次数N
for(j = 0; j< N*N; j++) 循环次数N^2
大O: O(n^3)

(4)

for(i=0;i<N;i++) 循环次数N
for(j=0;j<N;j++) 循环次数N
for(k=0;k<N;k++) 循环次数N
大O: O(n^3)

(5)

for(i=0;i<N;i=i*2) 循环次数log(n)
大O: O(log(n))

参考链接

数据结构-算法时间复杂度

原文：https://www.cnblogs.com/ag-chen/p/14701613.html