Big O 符号解释

Source: Dev.to

引言

大 O 表示法描述了算法的运行时间随输入规模增长的方式。了解最常见的复杂度有助于编写更快、更具可扩展性的代码，并在早期发现性能问题。

O(1) – 常数时间

O(1) 算法无论输入规模如何，所需时间都相同。

var users = new Dictionary
{
    { 1, "Caique" },
    { 2, "Maria" },
    { 3, "Fernanda" },
};

var user = users[1];   // Dictionary lookup by key is O(1)

O(log n) – 对数时间

对数算法在每一步都将问题规模缩小一个常数因子（通常是 2）。经典例子是对已排序数组的二分查找。

int BinarySearch(int[] array, int target)
{
    int left = 0;
    int right = array.Length - 1;

    while (left  // example truncated in source
}

O(n) – 线性时间

对每个元素仅遍历一次的简单循环运行时间为线性时间。

var users = new List { "Caique", "Maria", "Fernanda" };

foreach (var user in users)
{
    Console.WriteLine(user);
}

如果列表增长 10 %，循环的执行时间大约会增加 10 %。

O(n log n) – 线性对数时间

许多高效的排序算法（例如归并排序、快速排序）运行时间为 O(n log n)。

var numbers = new List { 5, 2, 8, 1, 3 };
numbers.Sort();   // .Sort() uses an O(n log n) algorithm internally

O(n²) – 二次时间

当算法包含一个嵌套循环，并且内部循环对整个输入进行遍历时，会产生二次复杂度。

var users = new List { "Caique", "Maria", "Fernanda" };

foreach (var user1 in users)
{
    foreach (var user2 in users)
    {
        Console.WriteLine($"{user1} - {user2}");
    }
}

操作次数随输入规模的平方成比例增长，这很快就会成为性能瓶颈。

结论

无论你是做前端还是后端，了解这些常见的大 O 模式都有助于在性能问题变得关键之前进行诊断和规避。应当在满足功能需求的前提下，尽可能选择最低的复杂度。