上述说法是一个很好的开始,但不是完全真实的。

更准确的解释(数学)

n = 输入参数数

T(n) = 表达算法运行时间的实际函数为 n 的函数

c = 常态

f(n)= 表达算法运行时间为 n 的函数的约定函数

接下来,在大O方面,接近f(n)被认为足够好,只要下面的条件是真实的。

lim     T(n) ≤ c×f(n)
n→∞

方程式是如 n 接近无限, T 的 n 是少于或等于 c 次 f 的 n。

T(n)∈O(n)

回到英语

基于上面的数学定义,如果你说你的算法是一个大O的n,这意味着它是一个函数的n(输入参数的数量)或更快。

Big O of n 意味着我的算法运行至少如此之快. 你不能看你的算法的 Big O 评分,并说它很慢. 你只能说它很快。

大O只是一种方式来“表达”自己,以一种常见的方式,“运行我的代码需要多少时间/空间?”

因此,你可能明白“n2”是什么意思,但要更具体,玩你的想法,你有一个简单的,最简单的分类算法;泡沫分类。

我的名单

比较 1 和 6 是最大的? Ok 6 是正确的位置,前进! 比较 6 和 3, oh, 3 是更少的! 让我们移动, Ok 列表改变了,我们需要从现在开始!

為每個項目,你再看所有項目一次,為比較,這也是“n”,所以為每個項目,你看“n”時刻意味著n*n = n2

我希望这就像你想要的那样简单。

要做一个字面类似,你不关心跑者能跑到100米,甚至跑到5K的速度,你更关心马拉松人,最好是超级马拉松人(除此之外,跑的类似性会崩溃,你必须转向“长跑”的形象意义)。

关于所有这些数学逻辑和多元化是什么? 显然算法与这些数学术语内在相关。 如果你测量区块上的所有孩子的高度,它会花费你那么多时间,因为有孩子。 这是内在相关的 n^1 或只是 n 的概念,在那里 n 是区块上的孩子数量。

我希望我已经解释说,大O的评级仅仅是关于长期,数学与计算方式有内在的联系,数学术语和其他简化与长期有相当常见的联系。

---

最简单的定义我可以给大 Oh 评分是:

智者可能已经意识到,我们可以表达操作的数量如:n2 + 2n. 但是,正如你从我们的例子中看到的两个数字的百万数字左右,第二个术语(2n)变得毫无意义(计算为0.0002%的总操作在这个阶段)。

因此,要找到一个名字给了电话号码(逆转搜索):

最佳案例:O(1);预期案例:O(n)(为500,000);最糟糕案例:O(n)(为1000,000)。

旅行卖家

听起来很简单吗?再想一想。

聚合物时间

另一个我想快速提到的是,任何具有O(na)复杂性的算法都说具有多元复杂性,或者在多元时间可溶解。

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( )在哪里是测量。

查看更多: 这里

TLDR:Big O在数学术语中解释算法的性能。

较慢的算法倾向于在 n 运行到 x 或多个,取决于它的深度,而更快的,如二进制搜索运行在 O(log n),这使得它运行更快,因为数据集变得更大。

可以从算法中最复杂的线路计算大O看。

有了小型或未分类的数据集,Big O 可能令人惊讶,因为 n log n 复杂性算法如二进制搜索可以缓慢较小的或未分类的集,为一个简单的运行例子线性搜索与二进制搜索,请参见我的JavaScript例子:

https://codepen.io/serdarsenay/pen/XELWqN?editors=1011(下面的算法)

function lineerSearch() {
  init();
  var t = timer('lineerSearch benchmark');
  var input = this.event.target.value;
  for(var i = 0;i<unsortedhaystack.length - 1;i++) {
    if (unsortedhaystack[i] === input) {
      document.getElementById('result').innerHTML = 'result is... "' + unsortedhaystack[i] + '", on index: ' + i + ' of the unsorted array. Found' + ' within ' + i + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return unsortedhaystack[i]; 
    }
  }
}

function binarySearch () {
  init();
  sortHaystack();
  var t = timer('binarySearch benchmark');
  var firstIndex = 0;
  var lastIndex = haystack.length-1;
  var input = this.event.target.value;

  //currently point in the half of the array
  var currentIndex = (haystack.length-1)/2 | 0;
  var iterations = 0;

  while (firstIndex <= lastIndex) {
    currentIndex = (firstIndex + lastIndex)/2 | 0;
    iterations++;
    if (haystack[currentIndex]  < input) {
      firstIndex = currentIndex + 1;
      //console.log(currentIndex + " added, fI:"+firstIndex+", lI: "+lastIndex);
    } else if (haystack[currentIndex] > input) {
      lastIndex = currentIndex - 1;
      //console.log(currentIndex + " substracted, fI:"+firstIndex+", lI: "+lastIndex);
    } else {
      document.getElementById('result').innerHTML = 'result is... "' + haystack[currentIndex] + '", on index: ' + currentIndex + ' of the sorted array. Found' + ' within ' + iterations + ' iterations';
      console.log(document.getElementById('result').innerHTML);
      t.stop(); 
      return true;
    }
  }
}