C#算法设计与分析详解

目录

• 1. 什么是科学方法？？
• 1.观察
• 2.将问题规模和运行时间的关系量化
• 2.数学模型
• 近似
• 近似运行时间
• 成本模型
• 总结
• 3. 增长数量级的分类
• 4. 倍率实验
• 5.注意事项
• 6. 处理对于输入的依赖
• 7.内存
• 1. 对象
• 2. 链表
• 3. 数组
• 4. 字符串对象

作为程序员，开发完一段代码，实现了某个功能时，有必要知道：

我的程序需要多长时间？

是什么导致我的程序消耗很多内存？

比如，统计或者处理了一大批数据。影响这些问题的因素很多，例如，电脑的性能，数据的性质（值类型和引用类型的区别），使用的算法。想要为这些基础问题提供答案需要通过科学方法。

1. 什么是科学方法？？

它是科学家为获取自然界知识所使用的一系列大家认同的方法。

• 1. 细致地观察真实世界的特点，通常还要精确的测量
• 2. 根据观察结果提出假设模型
• 3. 根据模型预测未来的事件
• 4. 继续观察并核实预测的准确性
• 5. 如此反复直到确认预测和观察一致

这里我们不需要深究它，我们会使用数学分析（科学方法的一种）为算法成本建立模型，并使用实验数据验证这些模型。

科学方法的一条关键原则是可重现的，可证伪的。

1.观察

怎么定量测量程序的运行时间？
各种工具，谷歌浏览器...，计时器 Stopwatch
我们一般只需要近似值就可以了。
对大多数程序的第一个定量观察就是计算性任务的困难程度可以用问题的规模来衡量。什么是问题的规模？可以是输入的大小或是某个命令行参数的值（开发预估时间）。
另一个定量观察是运行时长和输入本身相对无关，它主要取决于问题模型。就是说，同样大小的输入量，程序运行时间是差不多的。如果换一批同样大小的数据，运行时长差很多，就需要控制运行时间对输入的敏感度（比如把实验数据存起来）。

2.将问题规模和运行时间的关系量化

• 1.生成实验数据
• 2. 数据分析

根据问题规模和运行时长的数据绘制图表
猜想

举例 ThreeSum 实验

public static int ThreeSum(int[] a)
        {
            int N = a.Length;
            int cnt = 0;
            for (var i = 0; i < N; i++)
            {
                for (var j = i+1; j < N; j++)
                {
                    for (var k = j + 1; k < N; k++)
                    {
                        if(a[i]+a[j]+a[k] == 0)
                        {
                            cnt++;
                        }
                    }
                }
            }

            return cnt;
        }

lg(T(N)) = 3 lgN + lga --a是常数
T(N) = aN^3
这里猜想的时候用到冥次法则：T(N) = aN^b

2.数学模型

虽然有很多复杂的因素影响着程序的运行时间，但一个程序的运行的总时间主要有关的两点是：

• 1. 执行每条语句的时长 （取决于计算机，编译器和操作系统）
• 2. 执行每条语句的频率 （取决于程序本身和输入）

计算执行每条语句的时长可以通过各种工具测出。

重点是判断执行每条语句的执行频率，有的语句很好判断，比如一些赋值语句；有些需要深入分析，比如ThreeSum 实验中 if 语句的执行次数为 N(N-1)(N-2) / 6 次（主要是要了解立方推导公式）。而且有些语句的执行次数取决于输入的数据，例如 计算和为 0 的三元组的数量的语句（0 ~ N^3 / 6）。

近似

频率分析可能会产生复杂冗长的数学表达式，例如：

N(N-1)(N-2) / 6 = N^3 / 6 - N^2 / 2 + N/3

我们使用波浪号逼近法，在其中我们丢弃使公式复杂化的低阶项。我们写〜f（N）表示当N增长时除以f（N）接近1的任何函数。我们写g（N）〜f（N）表示当N增长时g（N）/ f（N）接近1。

所以N^3 / 6 - N^2 / 2 + N/3 的 近似函数是N^3 / 6 ，增长数量级 是N^3 。

近似运行时间

大部分情况下，执行最频繁的语句决定了程序执行的总时间 - 内循环，ThreeSum 实验中的内循环就是 第三层循环和 if 语句。大部分程序的运行时间都只取决于某一小部分。

性质（猜想）：ThreeSum 的运行时间 ~ aN^3 （a 是常数），增长数量级是N^3。

成本模型

定义了所研究的算法的基本操作。

可以用一个成本模型来评估算法的性质。在这个成本模型下，我们可以用数字说明算法而非某个性质。

例如，ThreeSum 的成本模型是数组的访问次数（无论读写）。

性质：该算法访问了 ~ N^3 / 6 个整数三元组中的所有3个整数。

通过明确成本模型使给定程序所需的运行时间的增长数量级和程序算法真正成本的增长数量级相同。

总结

大多数程序，得到运行时间的数学模型所需的步骤：

• 1. 确定输入模型，定义问题的模型（该任务的困难程度）
• 2. 识别内循环
• 3. 根据内循环中的操作确定成本模型
• 4. 对于给定的输入，判断这些操作的执行频率

3. 增长数量级的分类

我们使用一些结构原语（普通语句，条件，循环，嵌套和方法调用）来实现算法，因此，成本增长的数量级通常是问题规模N的几个函数之一。

4. 倍率实验

步骤：

1.循环执行ThreeSum 方法，并且每次 N = 2 * N （2 是比例，可以调整）

2. 打印每次执行ThreeSum 方法的运行时长和上一次的比

3. 直到该比值趋近于 2^b （b 是常数）

public static void RatioTest()
        {
            Random rd = new Random();
            Stopwatch timer = new Stopwatch();
            int[] a = new int[125];
            for (var i = 0; i < 125; i++)
            {
                a[i] = rd.Next(-1000, 1000);
            }

            timer.Start();
            var res = ThreeSum(a);
            timer.Stop();
            var prev = timer.ElapsedMilliseconds;

            for (var N = 250; true; N = 2*N)
            {
                a = new int[N];
                for (var i = 0; i < N; i++)
                {
                    a[i] = rd.Next(-1000, 1000);
                }
                timer.Start();
                var _res = ThreeSum(a);
                timer.Stop();
                var time = timer.ElapsedMilliseconds;
                var ratio = (decimal)time / prev;
                //Console.WriteLine(a.Length + "\t" + time + "\t" + ratio);
                Console.WriteLine(ratio);
                prev = time;
                //Thread.Sleep(1000);
            }
        }

根据冥次法则公式可以推导出该比例是以 2 为底的对数。并且可以得出增长数量级的近似模型（N^b）：

a 为 比例数， c 为极限比值， b 为该算法增长数量级的指数。这里 b = 3。

这个实验对于比值没有极限的算法无效。

该方法可以简单地预测程序地性能并判断它们的运行时间大致的增长数量级。

使用该方法可以评估解决大型问题的可行性，比如可以预估一个大型问题的程序运行时间。同时也可以评估使用更快的计算机所运行的时间。

5.注意事项

在对程序的性能进行分析时，得到不一致或者有误导性的结果的原因有很多：

1.大常数

在去近似时，我们一般会忽略低阶项，但如果低阶项的系数很大时（例如 10^3 或 10^6），该近似就是错误的。所以我们要对可能的大常数敏感。

2. 非决定性的内循环

内循环是决定性因素的假设并不总是正确的。错误的成本模型可能无法得到真正的内循环，问题的规模也许没有大到对指令的执行频率的首项大大超过其他低阶项并可以忽略他们的程度。有些程序在内循环之外也有大量指令需要考虑。换句话说，成本模型需要改进。

3. 指令时间

由于大多数计算机系统都会使用缓存技术，所以每条执行所需的时间并不是总是相同。

4. 系统因素

如果计算机同时运行很多程序，会产生争夺资源的情况，这会影响实验结果。

5. 对输入的强烈依赖

在研究程序的运行时间的增长数量级时，我假设运行时间和输入相对无关。当这个条件不满足时，会得到不一致或者错误的结果。例如，ThreeSum 返回的不是三个整数为0的对数，而是是否存在。如果前三个整数就满足，该程序的运行时间的增长数量级为常数；如果输入不含有这样的三个整数，程序的运行时间的增长量级为立方级别。

6. 多个问题参量

ThreeSum 性能分析是仅需要一个参量的函数来衡量程序的性能，参量一般是输入的规模。但是，多个参量也是有可能的。例如白名单（一个整数列表 M 个，一个白名单整数列表 N个，返回整数列表中有多少个整数在白名单中存在）,运行时间一般和 M logN 成正比。

6. 处理对于输入的依赖

输入模型： 我们可以仔细模拟要处理的输入的种类。这种方法具有挑战性，因为该模型可能是不现实的。

最坏情况下的性能保证：不管输入什么，程序的运行时间都小于一定的范围（取决于输入大小）。这种保守的方法可能适用于运行核反应堆或心脏起搏器或汽车制动器的软件。

随机算法：提供性能保证的一种方法是引入随机性，例如快速排序和哈希。每次您运行算法时，都会花费不同的时间。这些保证不是绝对的，但是它们无效的机会小于您的计算机被闪电击中的机会。因此，这种保证在实践中与最坏情况的保证一样有用。

操作序列：对于许多应用程序，算法输入可能不仅是数据，还包括客户端执行的操作顺序。

均摊分析： 提供性能保证的另一种方法是通过记录所有操作的总成本并除以操作总数来将成本均摊。

7.内存

计算程序对内存的使用情况和运行时间一样重要。计算机中电路的很大一部分作用就是帮助应用程序保存一些值并在使用时取出。保存的值越多，需要的电路越多，需要的内存也越多。

.net 内存分配系统已经帮我们解决了内存问题。

.net 使用 8 位（64位）表示字节，每个基本类型需要的内存：

1. 对象

一个对象所使用的内存，需要将所有实例变量使用内存与对象本身的开销（一般是16字节，这些开销包括一个指向对象的类的引用，垃圾回收信息和同步信息）以及4个填充字节相加。

当我们说一个引用所占的内存时，指的是它所指向的对象所占的内存。对象的引用通常是一个内存地址，因此使用8个字节的内存（在64位计算机上）。

2. 链表

嵌套的非静态类需要额外的8字节。例如，如果 Node 类是嵌套类，基于链表的栈中一个Node对象需要 40 字节（16字节的对象开销，两个对象引用各需8字节，还有8字节的额外开销。为什么不需要填充字节）。

因为一个 Integer 对象需要24字节，所以一个含有 N 个整数的基于链表的表需要 32 + 64 N 字节（Stack 对象开销 16 字节，引用类型实例变量 8 字节，int 类型实例变量 4 字节，4个填充字节，每个元素64字节（一个 Node 对象40字节和一个Integer 对象 24 字节））

3. 数组

C# 中数组是引用类型，一般都会因为记录长度需要额外的内存。一个基础类型的数组一般需要24字节的头信息（16字节的对象开销，4字节用于保存长度以及4填充字节）再加上保存值所需的内存。例如一个 含有 N个 int 值的数组需要 24 + 4N (会被填充为 8 的倍数)

4. 字符串对象

String 的标准实现含有4个实例变量：一个指向字符数组的引用（8字节）和三个 int 值（各4字节）。第一个 int 值描述的是字符数组中的偏移量，第二个 int 值是字符串的长度。第三个值是一个散列值，它在某些情况下可以节省计算。总共需要40字节，这是除字符数组之外字符串所需的内存空间，加上字符数组的话是 40 + 24 + 2N = 64 + 2N。

但是，字符数组常常是在多个字符串之间共享的。因为 String 对象是不可变的，这种设计使 String 的实现能够在多个String对象中都含有相同的字符数组时节省内存。

当使用 SubString 创建了一个新的 String 对象（40字节），但它仍重用了相同的字符数组。

当涉及到函数调用时， 内存的消耗是一个复杂的动态过程。当调用一个方法时，系统会从内存中的一个特定区域为方法分配所需的内存（用于保存局部变量），这个区域叫做栈。当方法返回时，占用的内存将被返回给栈，所以，在递归调用中不要创建大型的对象。当使用 new 创建对象时，系统会在堆中分配所需的内存，而且对象会一直存在，知道没有任何对它的引用。

到此这篇关于C#算法设计与分析的文章就介绍到这了。希望对大家的学习有所帮助，也希望大家多多支持我们。