我想你是一名计算机程序员。也许你是计算机科学的新学生，或者你是一个有经验的软件工程师。不管你在这个领域处于什么位置，算法和数据结构都很重要。不仅仅是作为理论概念，而是作为用于创建业务问题解决方案的构件。
当然，你可能知道如何使用 C# List或Stack类，但是你明白隐藏着什么吗？如果没有，您是否真的在使用哪些算法和数据结构方面做出了最佳决策？
对算法和数据结构有意义的理解始于有一种方法来表达和比较它们的相对成本。
当我们谈论衡量算法的成本或复杂性时，我们真正谈论的是在输入集非常大时对算法进行分析。分析当输入数量变得非常大时会发生什么被称为渐近分析。当应用到十个、一千个、一千万个项目时，算法的复杂度是如何变化的？如果一个算法用一千个项目在 5 毫秒内运行，那么当它用一百万个项目运行时会发生什么，我们能说什么呢？需要 5 秒还是 5 年？你难道不想在你的客户面前解决这个问题吗？
这东西很重要！
增长率描述了算法的复杂性如何随着输入大小的增长而变化。这通常用大 0 符号来表示。大 O 符号使用大写的 O(“顺序”)和表示算法复杂性的公式。公式可能有一个变量 n ，代表输入的大小。以下是我们将在本书中看到的一些常见的订单函数，但这个列表并不完整。
一个 O (1)算法是一个复杂度不变的算法，不管输入大小有多大。1 并不意味着只有一个操作，也不意味着该操作需要很少的时间。可能需要 1 微秒，也可能需要 1 小时。关键是输入的大小不会影响操作所需的时间。
public int GetCount(int[] items)
{
return items.Length;
}一个 O ( n )算法的复杂度随着输入的大小线性增长。可以合理地预计，如果输入大小为 1 需要 5 毫秒，那么输入一千个项目将需要 5 秒。
通过寻找访问每个成员的循环机制，您通常可以识别出一个 O ( n )算法。
public long GetSum(int[] items)
{
long sum = 0;
foreach (int i in items)
{
sum += i;
}
return sum;
}一个 O (log n )算法是一个复杂度与其大小成对数的算法。许多分治算法都属于这一范畴。二分搜索法树 Contains 方法实现了 O (log n )算法。
线性算法，或称对数线性算法，是一种复杂度为 O ( n log n )的算法。一些分而治之的算法就属于这一范畴。我们看合并排序和快速排序的时候会看到两个例子。
一个 O ( n 2 )算法的复杂度是其大小的二次函数。虽然不总是可以避免的，但使用二次算法是一个潜在的迹象，表明您需要重新考虑您的算法或数据结构选择。随着输入大小的增长，二次算法的伸缩性并不好。例如，一个有 1000 个整数的数组需要 1，000，000 次运算才能完成。一个有一百万个项目的输入需要一万亿次操作。从这个角度来看，如果每个操作需要一毫秒才能完成，一个接收一百万个项目输入的 O ( n 2 )算法需要将近 32 年才能完成。将算法速度提高 100 倍仍需要 84 天。
当我们看冒泡排序时，我们会看到一个二次算法的例子。
当我们说一个算法是 O ( n )的时候，我们到底在说什么？我们是说算法平均是 O ( n )吗？还是我们在描述最好或最坏的情况？
我们通常指的是最坏的情况，除非一般情况和最坏的情况有很大的不同。例如，我们将在本书中看到算法平均为 O (1)，但周期性地变为 O ( n )(参见 ArrayList.Add )的例子。在这些情况下，我将把算法平均描述为 O (1)，然后解释复杂度何时变化。
关键是说 O ( n )不代表永远是 n 操作。可能会少，但不应该多。
当我们测量算法和数据结构时，我们通常谈论两件事之一:操作完成所需的时间量(操作复杂性)，或者算法使用的资源量(内存)(资源复杂性)。
运行速度快十倍但使用十倍内存的算法在具有大量可用内存的服务器环境中可能完全可以接受，但在可用内存严重受限的嵌入式环境中可能不合适。
在本书中，我将主要关注操作复杂性，但是在排序算法一章中，我们将看到一些资源复杂性的例子。
我们可能衡量的一些具体例子包括:
- 比较操作(大于、小于、等于)。
- 任务和数据交换。
- 内存分配。
正在执行的操作的上下文通常会告诉您正在进行什么类型的测量。
例如，当讨论在数据结构中搜索项的算法的复杂性时，我们几乎肯定是在讨论比较操作。搜索通常是只读操作，因此不需要执行分配或分配内存。
然而，当我们谈论数据排序时，假设我们谈论的是比较、赋值或分配可能是合乎逻辑的。在可能存在歧义的情况下，我将指出复杂性实际上指的是哪种类型的度量。
本书找到的代码示例可以在https://bit bucket . org/sync fusion/data _ structures _ 简洁 _part1/src 下载。