首页 > 代码库 > 算法手记附1 随机化输入与计时器
算法手记附1 随机化输入与计时器
1.随机化输入
在快速排序算法的使用中，发现其性能是不稳定的，它的速度取决于输入情况，最好的情况下复杂度为O（NlogN），最坏情况下为O（N^2).
最简单的优化方法是随机化输入，打乱输入数组顺序，这样可以将不良输入带来低劣性能的可能性降到最低，对于预测算法的运行时间是十分重要的。
考虑到，在c++中std标准库已有random_shuffle函数，其他语言也有类似方法，但c#并没有此标准函数，这样我索性自己实现一个。
设计：
这里按照最简单的O（N）来设计，需要N次交换，实现起来无疑很简单。
实现：
public class RandomShuffle { private static Random rd; private static int N; public static IComparable[] shuffle(IComparable[] a) { rd = new Random(); N = a.Length; for (var i = 0; i < N; i++) { var newPosition = rd.Next(N); var temp = a[i]; a[i] = a[newPosition]; a[newPosition] = temp; } return a; }}
总结：
这里使用迭代写起来会更简洁明了，但是大规模的迭代会导致线程栈StackoverflowException，所以使用循环会更安全。
2.计时器
衡量一个算法的性能主要有两个方面：运行时间与内存性能。算法分析中，运行时长是一个很重要的衡量指标，但准确测量给定程序的运行时长时间很困难的事情，不过幸运地是我们只需要近似的结果就可以了。
我们可以使用系统API来实现一个精度尚可的计时器，可以帮助我们验证算法的速度。
设计：
设计一个Stopwatch类，它的elapsedTime（）方法能够输出程序执行时间。它的实现基于.NET框架的DateTime类，能返回以毫秒/秒计数的结果。
实现：
public class Stopwatch { private static DateTime startTime; public Stopwatch(DateTime time) { startTime = time; } public void elapsedTime() { DateTime endTime = DateTime.Now; double time = (endTime.Hour - startTime.Hour) * 3600 * 1000 + (endTime.Minute - startTime.Minute) * 60 * 1000 + (endTime.Second - startTime.Second) * 1000 + (endTime.Millisecond - startTime.Millisecond); if (time > 1000) { time /= 1000; Console.WriteLine("time: " + time + "s"); } else Console.WriteLine("time: " + time + "ms"); } }
总结：
这样的计时器虽然精度不高，但是足以用来简单地评估算法的性能了。
算法手记附1 随机化输入与计时器
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。