复杂度分析(1)

文章目录

复杂度分析时间复杂度大O表示法 空间复杂度

复杂度分析

时间复杂度

第一段代码：

1 int cal(int n) { 2 int sum = 0; 3 int i = 1; 4 for (i <= n; ++i) { 5 sum = sum + i; 6 } 7 return sum; 8 }

如上所示代码，求 1,2,3…n 的累加和，从CPU的角度看，这段代码每一行都执行着类似的操作：读数据-运算-写数据。 我们假设每行代码执行的时间是一样的，为unit_time，在这个基础上，我们可以估算出这段代码的总的执行时间。 第2行和第3行都只执行一次，为2 * unit_time时间，第4行和第5行都执行了n遍，为 2n*unit_time时间，所以这段代码总的执行时间 T(n) 大概为：

T(n) = (2n + 2)*unit_time;

从上面的计算公式可看出，代码的总执行时间 T(n) 与每行代码的执行次数 n 成正比。

在来看下面的代码：

第二段代码：

1 int cal(int n) { 2 int sum = 0; 3 int i = 1; 4 int j = 1; 5 for (; i <= n; ++i) { 6 j = 1; 7 for (; j <= n; ++j) { 8 sum = sum + i * j; 9 } 10 } 11 }

如上代码所示，这是一个循环嵌套代码，同样假定每行代码执行时间都是一样的为 unit_time，第2，3，4行每行都执行一次，时间为3 * unit_time，第5，6行执行了n次, 时间为2n*unit_time，第7，8行执行了n²次，时间为2n² * unit_time，这段代码总执行时间T(n)为：

T(n) = (2n*n + 2n + 3)*unit_time;

大O表示法

T(n) = O(f(n));

T(n) 表示代码执行的时间；n 表示数据规模，f(n)表示每行代码执行的时间总和，因为 是一个公式，所以用f(n)表示，公式中的O代表 T(n) 与 f(n) 成正比。 大O表示法并不表示代码执行的具体时间，而是表示代码执行时间随数据规模增长的变化趋势。所有也叫渐近时间复杂度，简称时间复杂度。 因为大O表示法只表示时间趋势，所以在估算时间时，会忽略公式中的常量，低阶项。 如：

T(n) = (2n + 2)*unit_time 只取n作为估算，大O表示时间复杂度为： O(n)

T(n) = (2n*n + 2n + 3)*unit_time 只取n²，大O表示时间复杂度为： O(n²)

空间复杂度

1 void print(int n) { 2 int i = 0; 3 int[] a = new int[n]; 4 for (i; i <n; ++i) { 5 a[i] = i * i; 6 } 7 for (i = n-1; i >= 0; --i) { 8 print out a[i] 9 } 10}

如上代码所示，第3行代码申请了一个长度为n的整形数组，其它的代码占用的空间没有占用更多的空间，空间复杂度为：O(n)