Время работы - связанные списки полиномиальные

Question

Я разработал два алгоритма, и теперь они просят меня найти время работы. Проблема состоит в том, чтобы разработать отдельную связанную версию списка для манипулирования многочлены. Две основные операции добавление а также умножение.

В целом для списков запуск этих двух операций ($ x, y $ - это длины списков):

• Дополнение: время $ o (x+y) $, space $ o (x+y) $
• Умножение: время $ o (xy log (xy)) $, space $ o (xy) $

Может ли кто -нибудь помочь мне найти время работы моих алгоритмов? Я думаю, что для первого алгоритма это как указано выше $ O (x+y) $, для второго у меня есть две вложенные петли и два списка, так что это должно быть $ o (xy) $, но почему $ o (xy log (xy)) $ выше?

Это алгоритмы, которые я разработал (в псевдокоде):

 PolynomialAdd(Poly1, Poly2):
 Degree := MaxDegree(Poly1.head, Poly2.head);
 while (Degree >=0) do:
      Node1 := Poly1.head;
      while (Node1 IS NOT NIL) do:
         if(Node1.Deg = Degree) then break;
         else Node1 = Node1.next;
      Node2 := Poly2.head;
      while (Node2 IS NOT NIL) do:
         if(Node2.Deg = Degree) then break;
         else Node2 = Node2.next;
      if (Node1 IS NOT NIL AND Node2 IS NOT NIL) then
         PolyResult.insertTerm( Node1.Coeff + Node2.Coeff, Node1.Deg);
      else if (Node1 IS NOT NIL) then
         PolyResult.insertTerm(Node1.Coeff, Node1.Deg);
      else if (Node2 IS NOT NIL) then
         PolyResult.insertTerm(Node2.Coeff, Node2.Deg);
      Degree := Degree – 1;
 return PolyResult; 

 PolynomialMul(Poly1, Poly2): 
 Node1 := Poly1.head;
 while (Node1 IS NOT NIL) do:
      Node2 = Poly2.head;
      while (Node2 IS NOT NIL) do:
           PolyResult.insertTerm(Node1.Coeff * Node2.Coeff, 
                              Node1.Deg + Node1.Deg);
           Node2 = Node2.next;                 
      Node1 = Node1.next;
 return PolyResult;

InsertTerm вставляет термин в правильном месте в зависимости от степени термина.

 InsertTerm(Coeff, Deg):
 NewNode.Coeff := Coeff;
 NewNode.Deg := Deg;
 if List.head = NIL then
    List.head := NewNode;
 else if NewNode.Deg > List.head.Deg then
    NewNode.next := List.head;
    List.head := NewNode;
 else if NewNode.Deg = List.head.Deg then 
    AddCoeff(NewNode, List.head);
 else
    Go through the List till find the same Degree and summing up the coefficient OR
    adding a new Term in the right position if Degree not present;

Answer 1

Время бега InsertTerm Подпрограмма-это $ theta (n) $, где $ n $-это количество терминов в полиноме, и это сложность наихудшего случая, а также сложность среднего уровня отсутствует какую-либо информацию о вставке монома.

Внешняя петля PolynomialAdd пробеги MaxDegree(Poly1.head, Poly2.head) времена Внутри каждой итерации внутренние петли ищут узел с правыми степенями в каждом полиноме. Для условий степеней, которые отсутствуют в мономе или присутствуют в конце монома, время выполнения внутреннего цикла составляет $ theta (n) $, где $ n $ - это количество условий в соответствующем мономе. Время бега InsertTerm обсуждался выше; Здесь все, что мне нужно знать, это то, что это $ theta (n) $. Отсюда и время бега PolynomialAdd $ theta ( max (x, y) cdot (x + y)) $, где $ x $ и $ y $ - это количество условий в полиномах Poly1 а также Poly2 соответственно.

Количество звонков InsertTerm в PolynomialMul Это явно $ xy $, так как внешний цикл всегда работает в $ x $ времени, а внутренний цикл всегда работает в $ y $. Я предполагаю, что Node1.Deg + Node1.Deg это опечатка, и вы действительно имели в виду Node1.Deg + Node2.Deg. Анкет Я не дам здесь полного доказательства, но интуитивно говоря, это происходит в списке результатов, и поэтому в среднем время, проведенное в insertTerm примерно половина длины списка: $ theta (x+y) $. Поэтому время бега PolynomialMul является $ theta (x , y , (x+y)) $.

Можно внедрить полиномиальное добавление и умножение с более быстрым временем работы, но вам нужно улучшить свой код. Основная идея заключается в том, что вы тратите много времени на InsertTerm, Вставка в случайных позициях в список результатов. Вместо этого договориться о создании списка результатов по порядку: сначала термин с самой низкой степень термин высочайшей степени и поддержание указателя на next указатель в последнем узле). Кроме того, не пересекайте аргументы снова на каждой итерации через цикл: кроме того, одновременно итерация над двумя аргументами; В умножении, где вам нужно объединить термины разных степеней, помните, где вы остановились, чтобы вы могли начать снова с той же точки.

Answer 2

Алгоритм умножения имеет характеристику $ o ( log (n)) $, поскольку фактическая операция умножения может быть разделена на отдельные подзадачи, «умножьте». Но сложность становится хуже, когда вам придется снова пройти весь список результатов в подпрограмме «вставки», которая называется во внутренней петле вложенных петлей. Это делает количество данных $ n^n $, а сложность становится $ o ( log (n^n)) $, что эквивалентно $ o (n log (n)) $.