“什么是明确的英语解释大O?尽可能少的正式定义和简单的数学。

这样一个美丽简单而短暂的问题似乎至少值得一个同样短暂的答案,就像一个学生在教学期间可以得到的那样。

大 O 评级简单地说明一个算法可以运行多长时间,仅仅是输入数据的数量。

(在一个美妙的,无单位的时间感中!)(这就是重要,因为人们总是想要更多,无论他们生活在今天还是明天)

好吧,什么是那么奇妙的关于大O评级,如果这就是它做什么?

实际上,Big O分析是如此有用和重要,因为Big O把重点放在算法本身的复杂性上,完全忽略了一切只是比例性恒定的东西 - 如JavaScript引擎,CPU的速度,您的互联网连接,以及所有快速变成像模型T一样可笑的过时的东西。

定义 : 大 O 评级是指如果数据输入增加,算法性能将如何表现的评级。

当我们谈论算法时,有3个重要柱子 算法输入、输出和处理 大 O 是象征性的评分,如果数据输入增加到什么速度,算法处理的性能将有所不同。

例如,请参见下面的函数“函数1”,该函数收集并在第一个记录中进行处理,现在该函数的性能将是相同的,无论您放置1000、10万或100000记录。

void Function1(List<string> data)
{
string str = data[0];
}

void Function2(List<string> data)
        {
            foreach(string str in data)
            {
                if (str == "shiv")
                {
                    return;
                }
            }
        }

因此,通过查看Big O评级,我们分类算法的好和坏区域。

此分類上一篇

https://www.youtube.com/watch?v=k6kxtzICG_g

大 O 评分是描述一个算法的空间或运行时间的上限的一种方式. n 是问题的元素数量(即序列的尺寸,树上的节点数量等) 我们有兴趣描述运行时间,因为 n 变得大。

要说二进制搜索有运行时间的O(登录)是说有某些恒定的c,你可以增加登录(n)通过它将总是比运行时间的二进制搜索。

换句话说,g(n)是你的算法的运行时间,我们说g(n) = O(f(n))当g(n) <=c*f(n)当n > k,当c和k是某些恒定的。

f(x) = k(x)g(x) k 与 a(如果 a = +∞,这意味着有 N 和 M 等数,以至于每个 x > N 的, < M 等数。

sin x = O(x) when x → 0. sin x = O(1) when x → +∞, x2 + x = O(x) when x → 0, x2 + x = O(x2) when x → +∞, ln(x) = o(x) = O(x) when x → +∞。

更多例子

1(一) :

这种复杂性与O(1)相同,除非它只是稍微糟糕一点,对于所有实用目的,你可以把它视为一个非常大的连续规模。

和(n):

O(n log n):

O(n2):

它作为一个平方,在那里 n 是平方侧的长度. 这是与“网络效应”相同的增长率,在那里网络中的每个人都可以知道网络中的每个人. 增长是昂贵的. 大多数可扩展的解决方案不能使用这个复杂度的算法,而不做显著的体操。

二(二) :

这是一个非常简单的解释,但我希望它涵盖了最重要的细节。

让我们说你的算法处理问题取决于某些“因素”,例如,让我们做它N和X。

根据 N 和 X,您的算法将需要一些操作,例如在 WORST 案例中,它是 3(N^2) + log(X) 操作。

由于Big-O不太关心恒定的因素(aka 3),你的算法的Big-O是O(N^2 + log(X))。它基本上翻译“你的算法需要最糟糕的案例规模的操作数量”。