广西网站建设方案/优书网

用用C语语言言举举例例讲讲解解数数据据结结构构中中的的算算法法复复杂杂度度结结与与顺顺序序表表

数数据据结结构构算算法法复复杂杂度度

1、、影影响响算算法法效效率率的的主主要要因因素素

1)算法采用的策略和方法；

2 )问题的输入规模；

3 )编译器所产生的代码；

4 )计算机执行速度。

2、、时时间间复复杂杂度度

// 时间复杂度：2n + 5

long sum1(int n)

{

long ret = 0; \\1

int* array = (int*)malloc(n * sizeof(int)); \\1

int i = 0; \\1

for(i=0; i

{

array i] = i + 1;

}

for(i=0; i

{

ret += array i];

}

free(array); \\1

return ret; \\1

}

\\时间复杂度: n + 3

long sum2(int n)

{

long ret = 0; \\1

int i = 0; \\1

for(i=1; i<=n; i++) \\n

{

ret += i;

}

return ret; \\1

}

\\时间复杂度: 3

long sum3(int n)

{

long ret = 0; \\1

if( n > 0 )

{

ret = (1 + n) * n / 2; \\1

}

return ret; \\1

}

随着问题规模n的增大，它们操作数量的差异会越来越大，因此实际算法在时间效率上的差异也会变得非常明显！

判断一个算法的效率时，往往只需要关注操作数量的最高次项，其它次要项和常数项可以忽略。

在没有特殊说明时，我们所分析的算法的时间复杂度都是指最坏时间复杂度。

3、、空空间间复复杂杂度度

//空间复杂度：12 + n

long sum1(int n)

{

long ret = 0; \\4

int* array = (int*)malloc(n * sizeof(int)); \\4 + 4 * n

int i = 0; \\4

for(i=0; i

{

array i] = i + 1;

}

for(i=0; i

{

ret += array i];

}

free(array);

return ret;

}

\\空间复杂度: 8

long sum2(int n)