对冒泡排序复杂性的困惑
Confusion on Bubble sort complexity
从关于堆栈溢出我开始知道冒泡排序的最坏情况的复杂度是大哦= n^2
但我的困惑是它的推导方式是
Big Oh = n + n - 1 + n - 2 ... + 1 = (n(n + 1))/2 = O(n²)
现在方程 (n(n + 1))/2 = O(n²) 自相矛盾。
如果我取 n=10 那么 (n*(n + 1))/2 = 55 那么它怎么等于 n² 结果是 100 它实际上接近它的一半所以我们不能说它是 ~.
请解开我的疑惑。
时间复杂度的工作方式是您想要了解函数在非常大的值时的行为方式。您替换的值 N 将不准确，但它是大值的近似值。例如，如果 N = 1,000,000 并且您的时间复杂度为 O(n+1)，那么 1,000,000 和 1,000,001 是否不同？
我们的想法是，您保留那些渐近增长最快的项。因此，在 n*(n+1)/2 中，您将保留 n^2，因为它增长最快。
来自wikipedia：
f(x) = O(g(x)) as x goes to infinity if and only if there is a positive constant M such that for all sufficiently large values of x, the absolute value of f(x) is at most M multiplied by the absolute value of g(x).
所以在你的例子中有这样一个常数：如果我们取 M = 3 那么对于所有 n>0 不等式 (n*(n + 1))/2 < 3*(n^2) 成立。
此外，这个定义还说：O(n^2) = O(n^2/180) = O(n^2 + n)等等。
O 表示法旨在显示随着输入数量的增加，所需时间如何随着输入数量的增加而增加。例如，假设一段代码是 O(n)。如果我们要将输入加倍，我们预计 运行 时间会（大致）加倍。如果我们将它增加三倍，我们预计 运行 时间也会增加三倍。请注意，无论在 运行 代码时间的假设精确公式中可能存在任何因素，这都是正确的。
O(n^2) 也可以这样说：加倍会导致加倍，等等。
所以 :
O(n^2) == O(1/2*n^2) == O(2*n^2) == 0(1000000000*n^2)
这里是nice tutorial.
准确的说，O(...)是一组函数，而不是一个数字。有时有些人很懒，写 x = O(y) 而不是 x \in O(y).
您可以在 正式定义 列中找到集合 O(y) 的确切定义 table: https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations
这在非正式场合是什么意思？ O(f(x)) 包含的函数 增长 的速度大致相同。
举个例子，如果你有 g(x) = n^2 + 5n - 7000 那么它在 O(n^2) 中，因为 n^2 是函数的主要部分（与确切的定义相比）。
另外，常数因子也可以去掉。所以，g(x) = 1000n^2 也在 O(n^2).
因此，O(...) 仅指示某些变量取决于哪些变量以及多少变量。例如，存在一个输入（它可能非常大），其中函数 n^2 大于 100000000 * n.
因此，时间复杂度为 O(n^2) 的算法通常不如 O(n) 中的算法好。但是，这非常重要，在实践中它可能更可取，因为第二种算法中的隐藏内容可能非常大，以至于第一种算法对于实践中出现的输入大小更好。然而，输入大小有一个界限（它可以非常大），第二个算法会变得更好，但它们可能不会在实践中出现。
Now the equation (n*(n + 1))/2 = O(n^2) is contradictory.
不，不是。
因为它不是真正的方程式。
事实上，O(n^2) 是 无限函数集 f(n) 的简写，每个函数都有 属性：
limit ( n -> infinity ) of f(n) <= C * n^2 ... for some constant C.
（有更准确的表述方式...）
直觉上，f(n) 是集合的成员 O(n^2) 告诉我们 f(n) 与 [=15= 成比例增长] 因为 n 变得 真的 大。
很容易证明f(n) = (n*(n + 1))/2是集合O(n^2)
的成员
非正式地，由于 n 对于这个 f(n) 变得非常大，方程的 (n^2)/2 项占主导地位，n/2 消失得无足轻重。
任何排序算法的复杂性都取决于比较。在冒泡排序中，我们看到总共有 N-1 次通过。在第一遍中，进行 N-1 次比较以将最高元素放在正确的位置。然后在第 2 遍中，第二高的元素被放置在它的位置。因此，为了计算复杂度，我们必须计算算法所做的比较~
使用基本的离散数学~
f(n)= (n-1)+(n-2)+(n-3)+.....+ 3 + 2 + 1
f(n)= n(n-1)/2
f(n)= n^2 + O(n) ~ (The constans are ignored for deriving Complexities)
f(n)= O(n^2)
因此冒泡排序的复杂度为O(n^2)。这意味着执行冒泡排序所需的时间与 n^2 成正比，其中 n 是数组中的元素总数。
从
但我的困惑是它的推导方式是
Big Oh = n + n - 1 + n - 2 ... + 1 = (n(n + 1))/2 = O(n²)
现在方程 (n(n + 1))/2 = O(n²) 自相矛盾。
如果我取 n=10 那么 (n*(n + 1))/2 = 55 那么它怎么等于 n² 结果是 100 它实际上接近它的一半所以我们不能说它是 ~.
请解开我的疑惑。
时间复杂度的工作方式是您想要了解函数在非常大的值时的行为方式。您替换的值 N 将不准确，但它是大值的近似值。例如，如果 N = 1,000,000 并且您的时间复杂度为 O(n+1)，那么 1,000,000 和 1,000,001 是否不同？
我们的想法是，您保留那些渐近增长最快的项。因此，在 n*(n+1)/2 中，您将保留 n^2，因为它增长最快。
来自wikipedia：
f(x) = O(g(x)) as x goes to infinity if and only if there is a positive constant M such that for all sufficiently large values of x, the absolute value of f(x) is at most M multiplied by the absolute value of g(x).
所以在你的例子中有这样一个常数：如果我们取 M = 3 那么对于所有 n>0 不等式 (n*(n + 1))/2 < 3*(n^2) 成立。
此外，这个定义还说：O(n^2) = O(n^2/180) = O(n^2 + n)等等。
O 表示法旨在显示随着输入数量的增加，所需时间如何随着输入数量的增加而增加。例如，假设一段代码是 O(n)。如果我们要将输入加倍，我们预计 运行 时间会（大致）加倍。如果我们将它增加三倍，我们预计 运行 时间也会增加三倍。请注意，无论在 运行 代码时间的假设精确公式中可能存在任何因素，这都是正确的。
O(n^2) 也可以这样说：加倍会导致加倍，等等。
所以 :
O(n^2) == O(1/2*n^2) == O(2*n^2) == 0(1000000000*n^2)
这里是nice tutorial.
准确的说，O(...)是一组函数，而不是一个数字。有时有些人很懒，写 x = O(y) 而不是 x \in O(y).
您可以在 正式定义 列中找到集合 O(y) 的确切定义 table: https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations
这在非正式场合是什么意思？ O(f(x)) 包含的函数 增长 的速度大致相同。
举个例子，如果你有 g(x) = n^2 + 5n - 7000 那么它在 O(n^2) 中，因为 n^2 是函数的主要部分（与确切的定义相比）。
另外，常数因子也可以去掉。所以，g(x) = 1000n^2 也在 O(n^2).
因此，O(...) 仅指示某些变量取决于哪些变量以及多少变量。例如，存在一个输入（它可能非常大），其中函数 n^2 大于 100000000 * n.
因此，时间复杂度为 O(n^2) 的算法通常不如 O(n) 中的算法好。但是，这非常重要，在实践中它可能更可取，因为第二种算法中的隐藏内容可能非常大，以至于第一种算法对于实践中出现的输入大小更好。然而，输入大小有一个界限（它可以非常大），第二个算法会变得更好，但它们可能不会在实践中出现。
Now the equation (n*(n + 1))/2 = O(n^2) is contradictory.
不，不是。
因为它不是真正的方程式。
事实上，O(n^2) 是 无限函数集 f(n) 的简写，每个函数都有 属性：
limit ( n -> infinity ) of f(n) <= C * n^2 ... for some constant C.
（有更准确的表述方式...）
直觉上，f(n) 是集合的成员 O(n^2) 告诉我们 f(n) 与 [=15= 成比例增长] 因为 n 变得 真的 大。
很容易证明f(n) = (n*(n + 1))/2是集合O(n^2)
非正式地，由于 n 对于这个 f(n) 变得非常大，方程的 (n^2)/2 项占主导地位，n/2 消失得无足轻重。
任何排序算法的复杂性都取决于比较。在冒泡排序中，我们看到总共有 N-1 次通过。在第一遍中，进行 N-1 次比较以将最高元素放在正确的位置。然后在第 2 遍中，第二高的元素被放置在它的位置。因此，为了计算复杂度，我们必须计算算法所做的比较~
使用基本的离散数学~
f(n)= (n-1)+(n-2)+(n-3)+.....+ 3 + 2 + 1
f(n)= n(n-1)/2
f(n)= n^2 + O(n) ~ (The constans are ignored for deriving Complexities)
f(n)= O(n^2)
因此冒泡排序的复杂度为O(n^2)。这意味着执行冒泡排序所需的时间与 n^2 成正比，其中 n 是数组中的元素总数。