C#数据结构与算法系列（十六）：时间复杂度（上）

1.时间频度

介绍：

一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，他花费时间越多。一个算法中的语句执行次数称为语句频度或时间频度

举例说明：

比如计算1-100所有数字之和，我们设计的两种算法

            int total = 0;

            int end = 100;

            for (int i = 0; i <=end; i++)
            {
                total += i;
            }

            total = (1 + end) * end / 2;

举例说明：忽略常数项

 

 结论：

1)2n+20和2n随着n变大，执行曲线无限接近，20可以忽略

2)3n+10和3n随着n变大，执行曲线无限接近，10可以忽略

举例说明：忽略低次项

 结论：

1)2n^2+3n+10和2n^2随着n的变大，执行曲线无限接近，可以忽略3n+10

2)n^2+5n+20和n^2随着n的变大，执行曲线无限接近，可以忽略5n+20

举例说明：忽略系数

 结论：

1)随着n值变大，5n^2+7n和3n^2+2n,执行曲线重合，说明这种情况下，5和3是可以忽略的。

2)而随着n^3+5n和6n^3+4n，执行曲线分离，说明多少次方式关键

2.时间复杂度

一般情况下，算法中的基本操作语句的重复执行次数是问题规模n的某个函数，用T(n)来表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，

T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

T(n)不同，但时间复杂度可能相同， 如：T(n)=n²+7n+6 与 T(n)=3n²+2n+2 它们的T(n) 不同，但时间复杂度相同，都为O(n²)。

计算时间复杂度的方法：

用常数1代替运行时间中的所有加法常数  T(n)=n²+7n+6  => T(n)=n²+7n+1

修改后的运行次数函数中，只保留最高阶项  T(n)=n²+7n+1 => T(n) = n²

去除最高阶项的系数 T(n) = n² => T(n) = n² => O(n²)