какова временная сложность алгоритма трех сумм - PullRequest
Новая
       2

какова временная сложность алгоритма трех сумм

2 голосов
/ 04 октября 2019

это функция для нахождения трех чисел в массиве, сумма которых равна нулю. 

//helper function
bool isPresent(int*arr, int size, int index, int num)
{
    for (int i = index; i < size; i++)
    {
        if (arr[i] == num)
            return true;
    }
    return false;
}
bool threesum(int*arr,int size)
{
    int i = 0, j = 1;
    int sum = arr[i] + arr[j];
    while (i < size-2)
    {
        if (isPresent(arr, size, j + 1, -sum) == true)
        {
            cout << arr[i] << " + " << arr[j] << " + " << -sum << '\n';
            return true;
        }
        if (j == size)
        {
            i++;
            j = i + 1;
        }
        j++;
        sum = arr[i] + arr[j];
    }
    return false;
}

в функции ThreeSum есть два цикла, в то время как до размера второго массива isPresentвременная сложность равна O (n), поэтому временная сложность функции тройки должна быть O (n ^ 2), но хотя цикл повторяется больше времени из-за j, то есть временная сложность функции тройки равна O (n ^ 2) или O (п ^ 3)

Ответы [ 2 ]

3 голосов
/ 04 октября 2019

Это O (n ^ 3). Подумай, как я меняюсь с Дж. Предположим, n = 10. Сначала i = 0, j = 1. Я не стану 1, пока j = 10, а затем после этих шагов снова i = 1, j = 2. Это похоже на запись двух циклов типаэто: 

for(int i = 0; i < n; i++)
    for(int j = i+1; j < n; j++)
1 голос
/ 04 октября 2019

Наивным подходом является O (N³).

Чтобы увидеть, какие суммы из трех равны 0, все суммы вычислены, и существует N * (N-1) * (N-2) / 4 различных суммы.

Но вы можете легко улучшить эту границу, сначала проиндексировав числа, а затем вычислив все суммы пар, сохранив их в хеш-таблице, а затем просмотрите, существует ли отрицательный из сумм, и проверьте, не являются ли его компонентыеще не были использованы для вычисления суммы. Это дает O (N²).

https://en.wikipedia.org/wiki/3SUM

bool threesum(const vector<int>& numbers){
  std::unordered_map<int,size_t> index;
  for (size_t i=0;i!=numbers.size();++i) {
    index.insert({numbers[i],i});
  }
  for (size_t i=0;i!=numbers.size();++i) {
    for (size_t j=i+1;j!=numbers.size();++j) {
      const int n = -(numbers[i]+numbers[j]); 
      if (index.count(n)) {
        if (index[n]==i) continue;
        if (index[n]==j) continue;
        return true; 
      }
    }
  }
  return false;
}
...