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

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

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

假设我们正在谈论一个算法A,该算法应该做一些与数据集的尺寸n。

然后 O( <某些表达式 X 涉及 n> ) 意思,在简单的英语:

如果您在执行 A 时不幸,可能需要尽可能多的 X(n) 操作完成。

正如发生的那样,有某些功能(想想它们作为X(n))的实施,这些功能往往很常见,这些功能是众所周知的,易于比较的(例子:1、Log N、N、N^2、N!等)。

比较这些,当谈到A和其他算法时,很容易根据他们可能需要完成的操作数量排序算法。

总的来说,我们的目标将是找到或结构一个算法A,以便它有一个函数X(n)返回尽可能低的数字。

它切断到骨头,只提供关于算法的规模性质的信息,具体如何使用资源(思考时间或记忆)的算法规模,以回应“输入大小”。

考虑蒸汽发动机和火箭之间的差异. 它们不仅仅是相同的东西的不同品种(如说,一个Prius发动机与一个Lamborghini发动机),但它们是显著不同的类型的驱动系统,在它们的核心。

statement;

是持久的. 声明的运行时间不会与 N 相比变化

for ( i = 0; i < N; i++ )
  statement;

for ( i = 0; i < N; i++ ) 
{
for ( j = 0; j < N; j++ )
  statement;
}

是四角形的,两条路的运行时间相当于N的平面,当N翻倍时,运行时间增加为N * N。

while ( low <= high ) 
{
 mid = ( low + high ) / 2;
 if ( target < list[mid] )
 high = mid - 1;
 else if ( target > list[mid] )
  low = mid + 1;
else break;
}

算法的运行时间是相当于 N 可以分为 2 次的次数。

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

是 N * log ( N ). 运行时间由 N 轮子(以色列或重复)组成,它们是 logarithmic,因此算法是线性和 logarithmic 的组合。

一般来说,做某些东西与每个项目在一个维度是线性的,做某些东西与每个项目在两个维度是四方的,并将工作区域分成一半是逻辑的。 还有其他大 O 测量,如圆形,曝光,和平方根,但它们不被报告为常见。 大 O 评分被描述为 O( )在哪里是测量。

查看更多: 这里

1(一) :

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

和(n):

O(n log n):

O(n2):

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

二(二) :

这里来了大O,告诉我们这个数学是多么艰难。

现在他们要求我添加一个到十个!为什么我会这样做?我不想添加一个到六个?添加一个到十个......好......这会更难!

对于大 n 而言, n 平方比 n 更大。

一个:我选择一张卡在我们现在工作的地板部分,你可以为我选择一个,如果你愿意(第一次我们这样做,“我们现在工作的地板部分”是整个地板,当然。

大 O 告诉我们:这个类型需要 O(n log n) 工作完成,在中间情况下。

现在你知道我的朋友,大O,他帮助我们做不到工作,如果你知道大O,你也可以做不到工作!

你和我一起学到了这一切!你太聪明了!谢谢你!

现在这个工作已经完成了,让我们玩吧!

---