C++数据结构中算法的使用

一.时间复杂度：

时间复杂度其实就是一个函数进行运算时执行的基本操作的次数；

运算分类的分析：

1.最坏的情况：任意输入规模的最大次数；

2.平均情况：任意输入规模等与平均次数；

3.最好的情况：任意输入规模的最少次数；

当然在实际情况下我们通常考量的最大运行次数，也就是任意输入规模，算法运行的最长时间，例如：

1.一个程序运行的最坏情况便是运行时间最长时间，同样也是一个程序的算法的上界；

2.对于有些算法，最坏情况出现的次数较为频繁；

3.当然平均情况和最坏情况一样差；

void test(int n)
{
   int i = 0;
   for(i = 0;i < n;i++)
   {
      for(int z = 0;z < n;z++)
      {
         int count = 0;
         count++;
      }
   }
   int j = 0;
   for(j = 0;j < n;j++)
   {
      count++;
   }
   int k = 5;
   while(k--)
   { 
      count++；
   }
}

这个函数的时间复杂度：f(n) = n^2 + n + 5；

时间复杂度，0渐进表示法

一个算法中语句总的执行次数称为语句的频度或时间频度，记为T(n)，n称为问题的规模。一般情况下，算法总的执行次数T(n)是问题规模(n)的某个函数f(n)，当n不断变化时，时间频度T(n)也会不断的变化，当n趋近于无穷大时，算法执行次数的增长率和

f(n)的增长率相同，记作T(n)= O(f(n))，称O(f(n))为算法的时间复杂度。

void Test4(int m, int n)
{
   int iCount = 0;
   for (int i = 0; i < 2*m ; ++i)
   {
      for (int j = 0; j < n ; ++j)
      {
          iCount++;
      }
   }
}

总执行次数：f(n) = 2*m*n == O(2*m*n)-->O(m*n)；

二.空间复杂度

空间复杂度的计算和时间复杂度相类似，都是通过大0的渐进表示法；

递归算法的空间复杂度的算法比如递归深度为n*每次递归调用的空间，如果递归调用的空间为常熟，则空间复杂度为0(n);

例如：

long long Fibonacci3( int n )
{
long long fibArray[3] = {0, 1, n};
for (int i = 2; i <= n ; ++i)
{
fibArray[2] = fibArray [1] + fibArray[0];
fibArray[0] = fibArray [1];
fibArray[1] = fibArray [2];
}
return fibArray [2];
}