时间戳

首页 > 解决方案 > 一半的假设是如何有 i < j 的？

algorithm - 一半的假设是如何有 i < j 的？

问题描述

我一直在阅读“Cracking the Coding Interview 6th Edition”。在第 0 章 - Big O 中，我无法理解对示例 3 中的问题所做的假设。

void printUnorderedPairs(int[] array){
  for(int i = 0; i < array.length; i++){
    for(int j = i + 1; j < array.length; j++){
      ...
    }
  }
}

在这意味着什么部分，它假设：

总共有 N^2 对。其中大约一半将具有 i < j，其余一半将具有 i > j。这段代码大约经过 n^2/2 对，所以它确实 O(N^2) 工作。

我的问题是，如何假设其中大约一半将完成 i < j 而剩下的一半将完成 i > j？有人可以向我解释一下吗？

谢谢！

标签： algorithmtime-complexity

解决方案

有几种方法可以尝试考虑这个假设，我非常喜欢@IanMercer 在评论中的“几何”建议。这是另一个：

什么是无序对
无序对是一对整数(i,j)，其中i和j位于域中(1, N)。（它们可以取从 1 到 N 的任何值）。

有几对？
i可以是从 1 到 的任何值N，也j可以是从 1 到 的任何值N。任何组合i形成一个有效的对。所以有N*N对。

在所有对中，有多少对i < j
请注意，对于任何小于的对(a,b)，都存在一个对应项（相同的值但被翻转）。所以有相同数量的对，其中有对'i>j'。ab(b,a)i<j

那么这个令人困惑的部分大致是什么？这是因为所有这些N*N对都有一些既不是i<j也不是j>i，而那些正是那些N对i==j。

因此，这些N*N对分为三个部分和。由于前两个组与仅包含元素的最后一组相比要大得多，我们可以说大约有一半具有.(those where i < j)(those where j> i)(those where i==j)O(N**2)/2Ni<j

推荐阅读