Quad время сочетания сложности

Question

я наткнулся на этой проблеме: Учитывая массив чисел обр и ряд S, 4 различных чисел в обрах этой суммы до S.

где решение:

function findArrayQuadCombination(arr, S): 
    if (arr == null OR S == null): 
     return null 
    n = length(arr) 
    if (n < 4): 
     return null 
    # hashing implementation language dependent: 
    pairHash = new HashTable() 
    for i from 0 to n-1 
     for j from i+1 to n-1 
     if !pairHash.isMapped(arr[i]+arr[j]): 
      pairHash.map(arr[i]+arr[j], []) 
     pairHash.get(arr[i]+arr[j]).push([i, j]) 

    for pairSum in pairHash.getKeys() 
     if pairHash.isMapped(S - pairSum): 
     pairsA = pairHash.get(pairSum) 
     pairsB = pairHash.get(S - pairsSum) 
     combination = find4Uniques(pairsA, pairsB) 
     if (combination != null): 
      return combination 
    return null 

# Helper function. 
# Gets 2 arrays of sub-arrays of 2 numbers 
# Gets 4 unique numbers, from 2 sub-arrays of different arrays 
function find4Uniques(A, B): 
    lenA = length(A) 
    lenB = length(B) 
    for i from 0 to lenA-1: 
     for j from 0 to lenB-1: 
     if (A[i][0] == B[j][0] OR A[i][1] == B[j][1] OR 
       A[i][0] == B[j][1] OR A[i][1] == B[j][0]): 
      continue 
     else: 
      return [A[i][0], A[i][1], B[j][0], B[j][1]] 
    return null 

Решение говорит, что это O (n^2), но я не согласен.

Леной и lenB в find4Uniques может быть не более п^2 в длину так, find4Uniques представляет собой О (п^4) «За pairSum в pairHash.getKeys()» линии О (п^2), потому что может быть n^2 разных ключей. Значит, не все должно быть O (n^6)?

Answer 1

Для сложности, которая должна быть O(n^6), длины, которые вы указали, должны быть истинными одновременно. Кроме того, раннее возвращение в конечном цикле не могло быть вызвано, и длины должны были бы быть возможными, если бы были математические ограничения комбинаций сумм.

Проблема в том, что длины зависят друг от друга.

Если у вас были ключи n^2, их значения теперь могут иметь длину 1, так как каждая пара должна была бы суммироваться до другого значения.

Если список имел длину n^2, тогда все пары суммировались бы с одним значением, так что теперь есть только 1 ключ.

Если оба lenA и lenB были n^2, то вы получите непустое возвращение из find4Uniques по меньшей мере, одной из комбинаций, выходящее весь алгоритм, поэтому он не может быть запущен n^2 раз, а также.

Чтобы показать сложность во времени, вам необходимо указать фактическое значение arr и S, которые придают эту сложность.

Answer 2

Если все значения в arr отличаются, то find4Uniques вернет значение в течение 3 итераций внутреннего цикла, если B имеет размер 3+. Это делает все вызовы find4Uniques ограниченные сверху суммой размеров массивов, которые могут быть переданы для A. Который является числом пар элементов в arr и является O(n^2).

Однако, если значения в arr НЕ ОТНОСЯЩИЕСЯ, то это не обязательно должно быть выполнено. В частности, если S = 6 и arr = [0, 0, ..., 0, 1, 1, ..., 1, 4, 4,..., 4] то ответ null но pairSum == 1 мы будем иметь O(n^2) значение в A, что все выглядят как [0, 1] встречи O(n^2) значения в B, что все выглядят как [1, 4] и будут делать O(n^4) работы.

Однако исправление этой ошибки может быть легко выполнено путем простого удаления arr.