另一个关于大O符号的文章
对大O估计过程的另一种观点。
引言
我不确定是否有人在CodeProject上发表过关于大O表示法的文章。在其一封电子邮件通讯中，确实推荐了一篇：一位自学程序员解释的大O表示法。
实际上，考虑到他的背景和Justin涵盖的内容，这项工作做得非常好。我喜欢他用口香糖机来展示数量级如何指示大小的例子。我确实希望他能深入讲解用来算出200颗口香糖的数学。我也认为这是一篇很好的读物，涵盖了大O的基本概念（除了一个小疏漏）。
他的一个观点是大O是性能的预测器。对我来说，这是使用它的主要原因。我将把他涵盖的内容扩展到另外两种表示法。O(LogN)在其他文章中有相当充分的记录。我只是看到O(NLogN)被随意提及，而没有看到关于它的文章。即性能随着表示法的变化而越来越差：1、LogN、N、NLogN和N^2。（N^3会更差，但我还没有看到任何使用它的算法或讨论它的文章。）
如果你知道其他（相对常见的）表示法，我很想听听。
背景
两年前，我唯一知道的大O是一个关于一个男人和他“赛博格”的漫画。（不准确，但机器人也是。那个节目中的另一个成员确实是机器人。）然后在一个工作测试中，我被问到了大O。我承认我对此一无所知，然后上网搜索，并解释了我发现的关于它的信息以及在我阅读之前我所知道的关于它的信息。
网上存在一些错误信息，主要是因为人们并不了解他们在写什么。（似乎网上关于任何主题都有很多好坏信息。）
例如，根据网络评论，O(LogN)需要使用自然对数来计算对数。这完全是错误的。我承认很多文本使用logn来指代以e为底的对数（自然对数）。更常见的是将其列为“ln”或“loge”。仅仅列为“log”通常指的是以10为底的对数。这里可以使用任何底数，但两者都与O(LogN)没有直接关系，O(LogN)的直接关系是以2为底的N的对数。底数与LogN的预测性质无关。每一种存在的对数底数都会给出完全相同的预测。（N1需要“x”秒，N2应该需要多少？）
我可能被告知了e的定义原因并忘记了，但对我来说，它似乎没有什么自然或合理之处。维基百科甚至没有解释e的来源。我还没有弄清楚自然对数比起任何其他对数有什么用（除了大多数计算器都内置了它）。
更新！感谢读者的评论，我知道e的来源了。我说过，无论使用哪种对数底数，值的比率都是相同的。常数幂的图表的斜率将是e^(loge(常数^幂))。同样，使用相同底数的任意两个对数在比较两个数时会给出相同的比率。自然对数在这种计算中无关紧要，因子会不同，但比率完全相同。
对数基于底数的幂。对数的特点是，如果你想将两个值相乘，你可以将两个对数值相加，然后取底数的幂，这等于在不使用对数的情况下将两个原始数字相乘。所以，在比较数字时，无论使用哪种对数底数，对数的比率都是完全相同的。例如，2与8，10与1000，1000与10亿，无论使用哪种对数底数，它们都是一比三的比率。2与1024是一比十的比率。
Justin有一个O(N)的例子，即在一个值数组中查找1个值。你可以通过传递一个已排序的数组（而不是随机分布）来将其更改为LogN。将起始值（st）设置为0，将结束值（en）设置为长度减1。验证数字是否在范围内且不是端点，然后像二分查找逻辑一样，不断获取中间索引（mi = (st+en)/2）来将数组分成已排序的两半。如果找到数字，则返回true。如果mi等于st且未找到记录，则返回false。否则，将st（低）或en（高）设置为mi以将列表减半。如果你有1024个项目，你可以在10步内找到答案。对于512以上的任何项目数，步数相同。对于十亿个项目的列表，你可以在30步内找到匹配项。这是O(LogN)工作原理的基本解释。
对数就是对数，无论底数是e、10、2还是任何大于1的数字，它都完全相同。以2为底的2的对数是1，4是2，8是3。取2的自然对数，乘以3，然后将e取幂，答案是8。无论使用哪种对数底数，这始终是答案。
一种很少被提及的大O表示法是NlogN。这是N乘以N的对数，由于在大O文章中的覆盖，它似乎比你想象的更常见。
使用算法
我将不详细介绍代码，但我将提供运行O(N^2)（冒泡排序将N平方来处理。你将N加倍，处理时间应该会增加4倍）和运行O(NLogN)（二分排序）的代码。
下表显示了二分排序和冒泡排序之间性能差异的测试统计数据。
“Number”是我放在数组中的int字段的数量。我在200K个项目后停止了冒泡排序测试。（当项目加倍时，它会持续使时间翻四番，在200K时需要超过2分钟，而二分排序则需要0.04秒来排序相同数量的项目。）我想找出在相同2分钟时间限制内使用二分排序可以排序多少个项目，但在200M时耗尽了精力（RAM）。基本上，二分排序是一个NlogN的过程。即N乘以logN。正如文章所说，它是对最大时间的度量。在我的机器上，使用以10为底的对数，乘以N * Log * 3.84E-8 可以估算出排序（使用以10为底的logN）的秒数。如果你想要一个不同对数底数的乘数，可以使用相同的数学方法来获得该底数值。（例如，自然对数会得出一个不同的数字，你可以用它代替3.8...）我估计我的机器需要2.5年才能用冒泡排序完成1.5亿个项目的排序。
更新！快速排序是用户提供的一个链接。它是对二分排序的另一种描述，并更详细地介绍了算法。它使用了一些我不太理解的数学，但它表明最坏情况的性能损失比最佳情况慢39%。即，如果你对一个已排序的数组重新运行排序，它应该需要原始随机填充数组排序时间的72%到100%。我估计有很高的概率小于85%。
你应该能够轻松地调整测试软件，对已排序的数组运行第二次排序测试，看看它有多快。
Number: Number of items being sorted
Bubble: Time to sort using bubble sort
Binary: Time to sort using Binary Sort algorithm
Note that I stopped Bubble testing at 200K,
I estimate 150M (750 times larger) would take 79M seconds (2.5 years) on my machine.
LOG(Num;10)*Num: Basically what it says, the log base 10 of the Number times the Number (NLogN)
Secs/(LOG(Num;10)*Num): The ratio of the time taken for the binary sort divided
by NLogN. If exactly that kind of process, this should be constant.
(IE a sorted array should sort faster because it will consistently divide
in half. The random distribution shouldn't divide exactly in half
but it should be close enough to look constant.)
在我的机器上，以10为底的良好估计是3.8E-8或0.000000038。我的机器上的时间只以毫秒为单位增加，所以前两个糟糕的结果是由于计时四舍五入错误。请注意，不同的对数底数会有不同的常数，但它应该一致地提供相同的估计。例如，以2为底的对数可以通过将以10为底的N的对数除以2的以10为底的对数来计算（接近0.3）。
| 数字 | Bubble | 二进制 | LOG(Num;10)*Num | Secs/(LOG(Num;10)*Num) | BinSecs |
| 1,000 | 3ms | 0 | 3000 | 0.00E+000 | 0.000 |
| 10,000 | 304ms | 2ms | 40000 | 5.00E-008 | 0.002 |
| 100,000 | 30.667s | 19ms | 500000 | 3.80E-008 | 0.019 |
| 200,000 | 140.418s | 40ms | 1060206 | 3.77E-008 | 0.040 |
| 1,000,000 | 228ms | 6,000,000 | 3.80E-008 | 0.228 | |
| 10,000,000 | 2.645s | 70,000,000 | 3.78E-008 | 2.645 | |
| 90,000,000 | 27.481s | 715,881,825.85 | 3.84E-008 | 27.481 | |
| 150,000,000 | 46.372s | 1,226,413,688.86 | 3.78E-008 | 46.372 |
关注点
除非有非常充分的理由或只是玩玩，否则不要尝试使用系统免费提供的代码。（我在玩。Array.Sort比我的二分排序稳定快1.5倍。即，它也是O(NLogN)，但效率更高。）Justin的小疏漏？写O(1)然后提到拥有一百万个项目不会影响它。O(1)无法处理N个项目，因为你最多只能做到O(LogN)。如果你将O(1)应用于一百万个项目，它就变成了O(N)。口香糖球体的数学支持Justin的200这个数字。我数了12个口香糖球滚过。周长是2πR，所以R大约是4。也就是说，12个口香糖球并不是直线滚过的，口香糖球的球形意味着你不能在不留空隙的情况下堆积它们，所以让R为3.5。
我不得不查了球体的公式——4/3πr^3。再次四舍五入，对于半径3.5，有超过170个口香糖球。R为4时超过250个。数量级估计200是一个很好的数字。当我第一次读到二分排序时，作者说它在已排序的列表中表现不佳，我已经忘记了他具体是怎么做的，但他基本上是选择列表中的第一个项目作为中间值。（这使得一个已排序的列表成为N^2的过程）。我对自己说：“管他呢，让它在已排序和未排序的列表中都表现良好。”我还想，与其将所有较小的数字移到左边，不如假设它会命中中间值，然后将中间值向左或向右移动。
代码
以下是冒泡排序的C#代码，一种替代的冒泡排序（循环次数是其四分之一但仍是N^2），二分排序例程和测试代码（可以在控制台应用程序上运行）。
/// <summary>
/// Example Bubble Sort provided in article I read
/// </summary>
/// <param name="ar" />int array to be sorted
public static void BubbleSort(int[] ar)
{
for (int pass = 1; pass < ar.Length; pass++)
for (int i = 0; i < ar.Length - 1; i++)
if (ar[i] > ar[i + 1])
Swap(ar, i);
}
/// <summary>
/// Alternate version Bubble Sort. Cuts the number of loops by a Quarter
/// Faster than original. It in NO WAY is 4 times faster.
/// </summary>
/// <param name="ar" />int array to be sorted
public static void AltBubbleSort(int[] ar)
{
int endpoint = ar.Length, endOfFrst = ar.Length / 2 + 1;
for (int i1 = 0; i1 < endOfFrst; i1++)
{
endpoint--;
for (int i2 = i1; i2 < endpoint; i2++)
{
if (ar[i2] > ar[i2 + 1])
Swap(ar, i2);//When inner loop finishes the largest int will be at endpoint + 1
if (ar[i1] > ar[i2])
Swap(ar, i1, i2);//When inner loop finishes the smallest int will be at i1
}
}
}
/// <summary>
/// swap two items of an array (Regular and Alternate Bubble Sort)
/// </summary>
/// <param name="ar" />int[] array to work a swap
/// <param name="first" />First of two positions to swap, second is calculated
private static void Swap(int[] ar, int first)
{
int hold;
hold = ar[ first ];
ar[first] = ar[first + 1];
ar[ first + 1 ] = hold;
}
/// <summary>
/// swap two items of an array (Binary Sort and Alternate Bubble Sort)
/// </summary>
/// <param name="ar" />int[] array to work a swap
/// <param name="i1" />First of two positions to swap
/// <param name="i2" />Second position
private static void Swap(int[] ar, int i1, int i2)
{
int hold = ar[i1];
ar[i1] = ar[i2];
ar[i2] = hold;
}
/// <summary>
/// Binary sort method with custom modifications. Recursive code splits array hopefully in half
/// and calls each half to sort them.
/// </summary>
/// <param name="ar" />int array to be sorted
/// <param name="start" />Starting index location in the array to be sorted
/// <param name="end" />Ending index location
public static void BinSort(int[] ar, int start, int end)
{
int middle, middlel, middlevalue, hold, left, right;
if (start > end)
{
hold = start;
start = end;
end = hold;
}
if (start < ar.GetLowerBound(0)) start = ar.GetLowerBound(0);
if (end > ar.GetUpperBound(0)) end = ar.GetUpperBound(0);
middle = start + (end - start) / 2;
left = middle - 1;
right = middle + 1;
if (ar[start] > ar[end]) Swap(ar, start, end);
if (ar[middle] > ar[start] && ar[middle] > ar[end]) Swap(ar, middle, end);
else if (ar[middle] < ar[start] && ar[middle] < ar[end]) Swap(ar, middle, start);
middlel = middle;
middlevalue = ar[middle];
//left moves lower, right moves higher. middlel/middle point
// to the middle value(s) that won't be sorted when this finishes
//start end don't change from this point forward
bool finished = false;
while (!finished)
{
while (left >= start && ar[left] < middlevalue) left--;
while (right <= end && ar[right] > middlevalue) right++;
if (left >= start && ar[left] == middlevalue) Swap(ar, left--, --middlel);
if (right <= end && ar[right] == middlevalue) Swap(ar, right++, ++middle);
if ((left >= start && ar[left] > middlevalue) &&
(right <= end && ar[right] < middlevalue))
Swap(ar, left--, right++);
if (left < start)
{
if (right <= end && ar[right] < middlevalue)
{//need to move the value on the right to the left side
Swap(ar, middlel, ++middle);
//Move what used to be to right of the middle value to the left
if (right != middle)
//after the right is moved to the left both pointers are shifted right
Swap(ar, right, middlel++);
else middlel++;
right++;
}
if (right > end) finished = true;
}
else if (right > end)
{
if (left >= start && ar[left] > middlevalue)
{
Swap(ar, middle, --middlel);
if (left != middlel) Swap(ar, left, middle--);
else middle--;
left--;
}
if (left < start) finished = true;
}
}
if (middlel - start > 1) BinSort(ar, start, --middlel);
else if (ar[middlel] < ar[start]) Swap(ar, middlel, start);
if (end - middle > 1) BinSort(ar, ++middle, end);
else if (ar[middle] > ar[end]) Swap(ar, middle, end);
}
/// <summary>
/// logic to run various sorting tests
/// </summary>
/// <param name="args" />Set up to act like "Main" argument list - should hold int numbers
static void testSort(string[] args)
{
DateTime start = DateTime.Now;
List<int> arraySize = new List<int>();
int size;
if (args.Length > 0)
{
foreach (string a in args)
if (int.TryParse(a, out size)) arraySize.Add(size);
}
else arraySize.Add(20000);
foreach (int sizes in arraySize)
{
int[] testArray3 = GenRandVals(sizes), testArray2 = new int[2],
testArray1 = new int[2], testArray4 = new int[2];
//The above chews up over 3 seconds With or without the List in Debug
TimeSpan span = new TimeSpan(DateTime.Now.Ticks - start.Ticks);
Console.WriteLine(string.Format(
"Time to generate and copy arrays: {0} of size: {1}", span.ToString(), sizes));
start = DateTime.Now;
List<int> listArray = new List<int>(sizes);
if (sizes <= 200000)
{
testArray2 = CopyArray(testArray3);
testArray1 = CopyArray(testArray3);
testArray4 = CopyArray(testArray3);
for (int i = 0; i < sizes; i++) listArray.Add(testArray3[i]);
span = new TimeSpan(DateTime.Now.Ticks - start.Ticks);
Console.WriteLine(string.Format("Time to load Arrays: {0}, Length {1}",
span.ToString(), listArray.Count()));
start = DateTime.Now;
listArray.Sort();
span = new TimeSpan(DateTime.Now.Ticks - start.Ticks);
Console.WriteLine(string.Format(
"Plus time to sort List<int> listArray: {0}", span.ToString()));
start = DateTime.Now;
BubbleSort(testArray1);
span = new TimeSpan(DateTime.Now.Ticks - start.Ticks);
Console.WriteLine(string.Format(
"Time to run original BubbleSort: {0}", span.ToString()));
start = DateTime.Now;
AltBubbleSort(testArray2);
span = new TimeSpan(DateTime.Now.Ticks - start.Ticks);
Console.WriteLine(string.Format(
"Time to run alternate BubbleSort logic: {0}", span.ToString()));
int misMat = 0;
for (int i = 0; i < sizes; i++)
if (testArray1[i] != testArray2[i]) misMat++;
if (misMat > 0)
Console.WriteLine("Alternate bubbleSort routine has " +
"an error. {0} missmatches found", misMat);
start = DateTime.Now;
SortedLinkedNumbers xxx, yyy = CopyLinkedArray(testArray3);
span = new TimeSpan(DateTime.Now.Ticks - start.Ticks);
Console.WriteLine(string.Format(
"Time to run SortedLinkedNumbers Sort logic: {0}, Length {1}",
span.ToString(), sizes));
}
start = DateTime.Now;
BinSort(testArray3, 0, sizes - 1);
span = new TimeSpan(DateTime.Now.Ticks - start.Ticks);
Console.WriteLine(string.Format(
"Time to run binary Sort logic: {0}, Length {1}", span.ToString(), sizes));
start = DateTime.Now;
if (sizes <= 200000)
{
int highCount = 0, lowCount = 0, misMatch = 0;
for (int i = 0; i < sizes; i++)
{
if (testArray3[i] < testArray4[i]) lowCount++;
if (testArray3[i] > testArray4[i]) highCount++;
if (testArray3[i] != testArray2[i] || testArray1[i] != testArray3[i])
misMatch++;
}
Console.WriteLine(string.Format("{0} Values were moved earlier in the array, " +
"{1} were moved later {2} didn't move.",
lowCount, highCount, sizes - (highCount + lowCount)));
if (misMatch > 0)
Console.WriteLine(string.Format(
"Error in sorting - array didn't exactly match. Error count {0}.", misMatch));
}
if (sizes > 5000000)
{
testArray3 = null;//Release the memory in the array
Thread.Sleep(20);//Give time to GC the released array
testArray3 = GenRandVals(sizes);
start = DateTime.Now;
Array.Sort(testArray3);
span = new TimeSpan(DateTime.Now.Ticks - start.Ticks);
Console.WriteLine(string.Format("Time to run Array Sort logic: {0}, Length {1}",
span.ToString(), sizes));
testArray3 = GenRandVals(10);
Thread.Sleep(20);
}
}
}
/// <summary>
/// creates a random array of positive/negitive numbers of the specified size
/// </summary>
/// <param name="sizeArray" />Size of the array to generate
/// <returns>The created array</returns>
public static int[] GenRandVals(int sizeArray)
{
if (sizeArray <= 0) throw (new Exception(string.Format("GenRandVals(int sizeArray)
called. sizeArray MUST be > 0. Value= {0} sent.", sizeArray)));
int[] vals = new int[sizeArray];
int range = int.MaxValue, diff = range / 2;
Random rand = new Random();
for (int i = 0; i < sizeArray; i++)
vals[i] = rand.Next(range) - diff;
return vals;
}
/// <summary>
/// copies values from one array into another one
/// </summary>
/// <param name="ar" />The array to be copied
/// <returns>copied array</returns>
public static int[] CopyArray(int[] ar)
{
int len = ar.Length;
int[] Cpy = new int[len];
for (int i = 0; i < len; i++)
Cpy[i] = ar[i];
return Cpy;
}
历史
- 在请求发布前花了些时间修改了文章。于2013年9月23日请求发布审核。
- 根据反馈和反馈中提供的链接，将小写o改为大写O。修正了BinSort逻辑，使其允许非零的起始索引，并消除了查找中间索引时可能发生的整数溢出。于2013年9月30日重新发布。
- 根据文章的反馈，在文章中添加了更多细节。于2013年10月1日发布。