解决问题方法的效率

前言

今天开始学习数据结构，纯属笔记。

解决问题方法的效率，跟 3 个方面有关：

1，数据的组织方式
2，空间的利用率
3，算法的巧妙程度

一、数据的组织方式

图书馆图书存取的例子。以什么方式存储（组织）图书，又以什么方式查找。方式不同，效率高低特千差万别。

The efficiency of problem-solving methods is related to the organizational structure of data.

二、空间的利用率

给定一个正整数，输出小于等于这个正整数的所有正数：

#include<stdio.h>

void PrintN(int count);
void PrintN2(int count);

void main()
{
    //PrintN(1000000);
    PrintN2(1000000);
}

void PrintN(int count)
{
    for(int i = 1; i <= count; i++)
    {
	printf("%d\n",i);
    }
    return;
}

void PrintN2(int maxValue)
{
    if(maxValue)
    {
       PrintN2(maxValue - 1);
       printf("%d\n",maxValue);
    }
    return;
}

当计算数量较小时，PrintN、PrintfN2 效果一样，但当计算量较大时，使用递归算法的 PrintN2，由于内存溢出，直接崩溃。

这两个函数在空间复杂度 S(N) 上的差距是显而易见的：

PrintN：S(N) = C，是一个常数，因为该函数只使用了一个临时变量 i，不存在函数调用。

PrintN：S(N) = C*N，因为每次递归都会把前段数据压入内存，递归 N 次，就压入 N 次。

The efficiency of problem-solving methods is also related to the utilization of space.

三、算法的巧妙程度

计算给定多项式在给定点 x = 1.1 处的值 f(1.1)

#include<stdio.h>
#include<math.h>

#define MAXN 10

double f1(int n, double a[], double x);
double f2(int n, double a[], double x);

void main()
{
   double a[MAXN];
   for(int i = 0; i < MAXN; i++)
   {
      a[i] = (double)i;
   }

   double result =  f2(MAXN,a,1.1);

   printf("%f\n",result);
   return;
}

double f1(int n, double a[], double x)
{
   double result = a[0];
   for(int i = 1; i<= n; i++) 
   { 
       result += (a[i] * pow(x,i)); 
   } 
   return result; 
} 

double f2(int n, double a[], double x) 
{ 
   double result = a[n]; 
   for(int i = n; i> 0; i--)
   {
      result = a[i - 1] + x * result;
   }
   return result;
}

代码中，f1 和 f2 都能实现题目的计算，但是 f2 在时间复杂度 T(n) 上小于 f1，n 越大，差距越明显。

原因是计算机执行加减法的速度远高于乘除法的速度。忽略加减法耗时只考虑乘除法耗时时：

f1 中，一共需要 1+2+3+4+…+n = (n² + n)/2 次乘法。时间复杂度：T(n) = C1*n² + C2*n

f2 中，一共需要 n 次乘法。时间复杂度：T(n) = C*n

所以时间差距就出来了。

The efficiency of the problem-solving method is related to the ingenious degree of the algorithm.