Как было сделано предположение, что половина будет иметь i <j?

Question

Я читал "Взлом кодирования 6-е издание" .. В главе 0 - Большой О, у меня проблемы с пониманием предположения, сделанного для проблемы в Примере 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. Этот код проходит примерно n ^ 2/2 пар, поэтому он выполняет O (N ^ 2).

Мой вопрос: как было сделано предположение о Примерно в половине у тех будет i j готово? Может кто-нибудь объяснить мне, пожалуйста?

Спасибо!

Answer 1

Есть несколько способов подумать об этом допущении, мне очень нравится предложение "geometryri c" от @IanMercer в комментариях. Вот еще:

Что такое неупорядоченная пара
Неупорядоченная пара - это пара целых чисел (i,j), где i и j находятся в домене (1, N) , (Они могут принимать любое значение от 1 до N).

Сколько существует пар?
i может иметь любое значение от 1 до N, и j может иметь любое значение от 1 до N. Любая комбинация i образует правильную пару. Таким образом, есть N*N пар.

Из всех пар сколько пар существует, что i < j
Обратите внимание, что для любой пары (a,b), где a меньше, чем b, существует аналог (b,a) (те же значения, но перевернутый). Таким образом, существует такое же количество пар, где i<j, поскольку есть пары '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)/2 по сравнению с последней группой, которая имеет только N элементов, мы можем утверждать, что примерно половина имеет свойство, что i<j.