Блог

Следующий алгоритм кода Грея взят из книги «Элементы программирования». Учитывая частично построенный результат, в котором все пары соседних элементов отличаются не более чем на один бит, он вычисляет следующий элемент, изменяя один бит последнего элемента в списке и выполняя рекурсивный вызов.

Как бы можно было оценить время его работы? Моя интуиция подсказывает, что 2^n в результате есть элементы, каждый из которых требует по крайней мере постоянного времени и не более O(n) для вычисления, поэтому нижняя граница будет по крайней мере 2^n . Правильно ли это вообще? Как я могу рассчитать верхнюю границу времени выполнения с учетом обратного хода — некоторые вычисления не заканчиваются, как я могу учесть это?

 public static Listlt;Integergt; grayCode(int numBits) {  Listlt;Integergt; result = new ArrayListlt;gt;(List.of(0));  directedGrayCode(numBits, new HashSetlt;Integergt;(List.of(0)), result);  return result;  }   private static boolean directedGrayCode(int numBits, Setlt;Integergt; history, Listlt;Integergt; result) {  if (result.size() == (1 lt;lt; numBits)) {  return differsByOneBit(result.get(0), result.get(result.size() - 1));  }   for (int i = 0; i lt; numBits;   i) {  int previousCode = result.get(result.size() - 1);  int candidateNextCode = previousCode ^ (1 lt;lt; i);  if (!history.contains(candidateNextCode)) {  history.add(candidateNextCode);  result.add(candidateNextCode);  if (directedGrayCode(numBits, history, result)) {  return true;  }  result.remove(result.size() - 1);  history.remove(candidateNextCode);  }  }  return false;  }   private static boolean differsByOneBit(int x, int y) {  int bitDifference = x ^ y;  return bitDifference != 0 amp;amp; (bitDifference amp; (bitDifference - 1)) == 0;  }