算法的渐近符号
Asymptotic Notation for algorithms
我终于认为我理解了函数 f(n) 夹在 相同的下限和上限之间意味着什么 class 等等可以描述为 theta(n).
举个例子：
f(n) = 2n + 3
1n <= 2n + 3 <= 5n for all values of n >= 1
在上面的例子中它很有意义，n的顺序在两边，所以f(n)夹在1 * g(n)和[=之间14=].
当我尝试不使用符号来考虑最佳或最差 情况 而是作为上限、下限或平均界限时，它也更加清晰。
所以现在我想我终于理解了这个和它周围的数学我回去访问这个页面：https://www.bigocheatsheet.com/ 看看各种搜索功能的 运行 次，突然又对那里有多少算法，例如冒泡排序，在两侧（上限和下限）没有相同的顺序，但使用 theta 来描述它们。
冒泡排序有 Ω(n) 和 O(n^2)，但 theta 值给出为 Θ(n^2)。如果函数的上界是 N^2 的顺序但函数的下界是 n 的顺序，它怎么会有 Θ(n^2)？
实际上，您提到的页面具有很强的误导性 - 即使不是完全错误。如果您分析算法的复杂性，首先必须指定场景：即您是在谈论最坏情况（默认情况）、平均情况还是最佳情况。对于这三种情况中的每一种，您都可以给出下限 (Ω)、上限 (O) 或紧限 (Θ)。
以插入排序为例。虽然该页面严格来说是正确的，因为最好的情况是 Ω(n)，但它也可以（更准确地说）说最好的情况是 Θ(n)。同样，最坏的情况确实是该页上所述的 O(n²)（以及 Ω(n²) 或 Ω(n) 或 O(n³)），但更准确地说是 Θ(n²)。
不幸的是，使用 Ω 总是表示最好的情况而 O 总是表示最坏的情况是一个经常犯的错误。外卖信息：场景（最差、平均、最好）和边界的类型（上、下、紧）是两个独立的维度。
我终于认为我理解了函数 f(n) 夹在 相同的下限和上限之间意味着什么 class 等等可以描述为 theta(n).
举个例子：
f(n) = 2n + 3
1n <= 2n + 3 <= 5n for all values of n >= 1
在上面的例子中它很有意义，n的顺序在两边，所以f(n)夹在1 * g(n)和[=之间14=].
当我尝试不使用符号来考虑最佳或最差 情况 而是作为上限、下限或平均界限时，它也更加清晰。
所以现在我想我终于理解了这个和它周围的数学我回去访问这个页面：https://www.bigocheatsheet.com/ 看看各种搜索功能的 运行 次，突然又对那里有多少算法，例如冒泡排序，在两侧（上限和下限）没有相同的顺序，但使用 theta 来描述它们。
冒泡排序有 Ω(n) 和 O(n^2)，但 theta 值给出为 Θ(n^2)。如果函数的上界是 N^2 的顺序但函数的下界是 n 的顺序，它怎么会有 Θ(n^2)？
实际上，您提到的页面具有很强的误导性 - 即使不是完全错误。如果您分析算法的复杂性，首先必须指定场景：即您是在谈论最坏情况（默认情况）、平均情况还是最佳情况。对于这三种情况中的每一种，您都可以给出下限 (Ω)、上限 (O) 或紧限 (Θ)。
以插入排序为例。虽然该页面严格来说是正确的，因为最好的情况是 Ω(n)，但它也可以（更准确地说）说最好的情况是 Θ(n)。同样，最坏的情况确实是该页上所述的 O(n²)（以及 Ω(n²) 或 Ω(n) 或 O(n³)），但更准确地说是 Θ(n²)。
不幸的是，使用 Ω 总是表示最好的情况而 O 总是表示最坏的情况是一个经常犯的错误。外卖信息：场景（最差、平均、最好）和边界的类型（上、下、紧）是两个独立的维度。