Сложность алгоритма 3sum

Question

Этот код находит, есть ли в отсортированном массиве три числа, которые складываются в данную сумму, но я не уверен, как рассчитать его временную сложность.Буду признателен за ваш вклад и идеи о том, как его улучшить.

Обратите внимание , что цикл for может сам себя сбросить в цикле.

/* function to find if there are 3 values in the 
sorted array that sum up to a given sum */
int IsSumOf3( int arr[], size_t size, int sum)
{
  int right, left, third;
  right = size-1;
  left = 0;
  while(arr[right] > sum && right > 1)
  {
      --right;
  }
  if(right == 1)
  {
      printf("returned false on right == 1 \n");
      return 0;
  }

  for(third = left+1; third < right; ++third)
  {
      int localSum = arr[right]+ arr[left]+ arr[third];
      if(localSum == sum)
      {
          printf("right |%d|, left |%d|, third |%d|\n",arr[right], arr[left], arr[third]);
          return 1;
      }
      if(localSum > sum)
      {
         --right;
         left = 0;
         third = left;
      }
      if(third+1 == right)
      {
          ++left;
          third = left;
      }
  }
  printf("returned false on exit\n");
  return 0;
}

int main()
{

    int A[] = { 1, 4, 6, 8, 10, 46 };

    IsSumOf3(A,6, 22);
    IsSumOf3(A,6, 11);
    IsSumOf3(A,6, 100);
    IsSumOf3(A,6, 3);

    return 0 ;
}

Answer 1

Во-первых, я предлагаю вам прокомментировать свой код: людям здесь будет проще помочь вам.Я также предлагаю вам сделать это проще: первый подход должен состоять в том, чтобы составить список из суммы 2 чисел, где сумма меньше ожидаемого результата, а затем попытаться найти третий элемент для каждого значения суммы 2-значенийlist.

Ваш алгоритм проходит через массив, пока не найдет правильный результат.На каждой итерации, если нет действительного результата, есть одно значение (левое или правое), которое больше не рассматривается.Итерации в худшем случае для массива из N элементов:

N + (N-1) + (N-2) ... + 2 + 1 = N * N / 2

Наконец, сложность равна O (N ^ 2).

PS: обратите внимание, что подсчет случая, когда left = right = третий не влияет на сложность, поэтому чтобы упростить вычисление, я просто сохранил его врассмотрение.

Answer 2

Вы просто проходите массив, нет вложенного цикла рекурсивного вызова, поэтому O (n)

Хорошо, теперь я прочитал контекст, да уже поздно ^^

Или, конечно, худший случай, когда значения не отсортированы, потому что вам нужно просмотреть все значения, поэтому N ^ 3.Здесь массив отсортирован.

Но вы используете только цикл, и даже вы перезапускаете его это казалось волшебным ... слишком волшебным, извините, но это не сработает, у вас нетнайти решение, например, с вектором {4, 6, 11, 12, 14, 19} и ожидаемой суммой 36, но 6+11+19==36

Я не отвечаю о сложности, LC делает, носложность актуальна пока алгоритм не работает?Просто сделайте return 0; со сложностью O (1) ^^

---

PS, потому что у меня были сомнения, я использовал брутальную силу , чтобы проверить

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

/* function to find if there are 3 values in the 
sorted array that sum up to a given sum */
int IsSumOf3( int arr[], size_t size, int sum)
{
  int right, left, third;
  right = size-1;
  left = 0;
  while(arr[right] > sum && right > 1)
  {
      --right;
  }
  if(right == 1)
  {
      /*printf("returned false on right == 1 \n");*/
      return 0;
  }

  for(third = left+1; third < right; ++third)
  {
      int localSum = arr[right]+ arr[left]+ arr[third];
      if(localSum == sum)
      {
      /*printf("right |%d|, left |%d|, third |%d|\n",arr[right], arr[left], arr[third]);*/
          return 1;
      }
      if(localSum > sum)
      {
         --right;
         left = 0;
         third = left;
      }
      if(third+1 == right)
      {
          ++left;
          third = left;
      }
  }
  /*printf("returned false on exit\n");*/
  return 0;
}

int brutal(int arr[], size_t size, int sum)
{
  int i,j,k;

  for (i = 0; i != size - 2; ++i) {
    for (j = i+1; j != size -1; ++j) {
      for (k = j+1; k != size; ++k) {
        if ((arr[i] + arr[j] + arr[k]) == sum) {
          /*printf("%d %d %d\n", arr[i], arr[j], arr[k]);*/
          return 1;
        }
      }
    }
  }

  return 0;
}

int main()
{
#define N 6

  int a[N];

  srand(time(NULL));

  for (;;) {
    int i;

    a[0] = rand() % N;

    for (i = 1; i != N; ++i) {
      a[i] = a[i - 1] + (rand() % (N - 1)) + 1; /* suppose must not be equals */
    }

    for (i = a[N-1] + a[N-2] + a[N-3] + 1; i != 0; i -= 1) {
      if (IsSumOf3(a, N, i) != brutal(a, N, i)) {
        int j;

        for (j = 0; j != N; j++)
          printf("%d ", a[j]);
        printf(" / %d\n", i);
        return 0;
      }
    }
  }

  return 0 ;
}