Является ли подход, который я использовал, чтобы найти сложность времени правильным? - PullRequest
Новая
       4

Является ли подход, который я использовал, чтобы найти сложность времени правильным?

0 голосов
/ 31 декабря 2018

Для следующей задачи я придумал следующий алгоритм.Мне просто интересно, правильно ли я рассчитал сложность алгоритма или нет.Проблема:
Учитывая, что в качестве входных данных указан список целых чисел, определите, есть ли два целых числа (не обязательно различающихся) в списке: k.Например, для k = 12 и списка [2,10,5,3,7,4,8] существует пара 3 и 4, такая что 3 × 4 = 12.

Мое решение: // Представьте себе A - список, содержащий целые числа 

for(int i=0; i<A.size(); i++)                O(n)
{
  for(int j=i+1; j<A.size()-1; j++)            O(n-1)*O(n-(i+1))
  {
    if(A.get(i) * A.get(j) == K)             O(n-2)*O(n-(i+1))
      return "Success";                      O(1)
  }
}
return "FAILURE";                            O(1)

O (n) + O (n-1) * O (ni-1) + O (n-2) * O (ni-1)) + 2 * O (1) =

O (n) + O (n ^ 2-ni-n) + O (-n + i + 1) + O (n ^ 2-ni-n) + O (-2n + 2i + 2) + 2O (1) =

O (n) + O (n ^ 2) + O (n) + O (n ^ 2) + O(2n) + 2O (2) =

O (n ^ 2)

Помимо моего полуалгоритма, есть ли более эффективный алгоритм?

Ответы [ 2 ]

0 голосов
/ 01 января 2019

Ваш алгоритм выглядит как O (n ^ 2) наихудший случай и O (n * log (n)) средний случай, потому что чем длиннее список, тем больше вероятность выхода из циклов перед вычислением всех n ^ 2 пар.

Возможен алгоритм с O (n) наихудшим случаем и O (log (n)) средним.В реальной жизни это было бы менее эффективно, чем ваш алгоритм, для списков, в которых коэффициенты K находятся в самом начале, или список короткий, и более эффективным в противном случае.(псевдокод не написан на каком-либо конкретном языке) 

var h = new HashSet();
for(int i=0; i<A.size(); i++)
{
  var x = A.get(i);
  if(x%K == 0) // If x is a factor of K
  {
    h.add(x); // Store x in h
    if(h.contains(K/x))
    {
      return "Success";
    }
  }
}
return "FAILURE";

HashSet.add и HashSet.contains в среднем имеют значение O (1) (но медленнее, чем List.get, даже если это также O (1)).Для целей этого упражнения я предполагаю, что они всегда работают в O (1) (что не совсем верно, но достаточно близко для работы правительства).Я не учел крайние случаи, такие как список, содержащий 0.

0 голосов
/ 01 января 2019

Давайте разберем, что в сущности делает предложенный вами алгоритм.

Для каждого индекса i (st 0 ≤ i ≤ n) вы сравниваете i со всеми уникальными индексами j (i ≠ j), чтобы определить: i * j == k.

Инвариант для этого алгоритма будет означать, что на каждой итерации сравниваемая пара {i, j} не сравнивалась ранее.

Эта реализация (при условии, что она компилируется и запускается без исключений времени выполнения, упомянутых в комментариях), выполняет в общей сложности сравнения nC2 (где nC2 - биномиальный коэффициент для n и 2 для выбора всехвозможные уникальные пары), и каждое такое сравнение будет вычисляться в постоянное время (O (1)).Обратите внимание, можно доказать , что nCk не больше, чем n ^ k.

Таким образом, O (nC2) обеспечивает более точную верхнюю границу для этого алгоритма - хотя с помощью обычной большой записи O этовсе равно будет O (n ^ 2), так как nC2 = n * (n-1) / 2 = (n ^ 2-n) / 2, который по-прежнему порядка n ^ 2.

ВВаш вопрос из комментариев:

Правильно ли использовать «i» в сложности, так как я использовал O (n- (i + 1))?

i - текущий индекс, тогда как на сложность вашего алгоритма влияет только размер вашей выборки, n.

IOW, общая сложность рассчитывается для всех итераций в алгоритмев то время как я ссылаюсь на конкретную итерацию.Поэтому некорректно использовать «i» в ваших расчетах сложности.

Кроме моего полуалгоритма, есть ли более эффективный алгоритм?

Ваш«Полуалгоритм» кажется мне наиболее эффективным способом решения этой проблемы.Любой алгоритм, основанный на сравнении, потребует запроса всех пар в массиве, что соответствует сложности, описанной выше.Хотя я не рассчитал нижнюю границу и мне было бы интересно услышать, если кто-нибудь знает о более эффективной реализации.

edit: Другой ответ здесь показывает хорошее решение этой проблемы, которое(вообще говоря) более эффективный, чем этот.

...