Как найти все номера такси меньше N?

Ответ 1

Временная сложность алгоритма не может быть меньше O (N ²) в любом случае, так как вы можете печатать до O (N ²) номера такси.

Чтобы уменьшить использование пространства, теоретически можно использовать предложение, упомянутое здесь: небольшая ссылка. В принципе, идея состоит в том, что сначала вы пытаетесь использовать все возможные пары a, b и находите решение для этого:

a = 1 - (p - 3 * q) (p ² + 3 * q ²)

b = -1 + (p + 3 * q) (p ² + 3q ²)

Затем вы можете найти подходящую пару c, d, используя:

c = (p + 3 * q) - (p ² + 3 * q ²)

d = - (p - 3 * q) + (p ² + 3 * q ²)

и проверьте, меньше ли они меньше N. Проблема заключается в том, что решение этой системы уравнений может немного запутаться ( "немного" я ​​имею в виду очень утомительно).

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

Я надеюсь, что это помогло!

Ответ 2

Но это занимает пространство N ^ 2. Можем ли мы лучше?

Существует пространственное решение O (N) на основе очереди приоритета. Сложность времени O (N ^ 2 logN). Чтобы набросать идею алгоритма, вот матрица M такая, что M [i] [j] = я ^ 3 + j ^ 3 (конечно, матрица никогда не создавалась в памяти)

0 1 8 27 64 125 1 2 9 28 65 126 8 9 16 35 72 133 27 28 35 54 91 152 64 65 72 91 128 189 125 126 133 152 189 250
Обратите внимание, что каждая строка и каждая строка сортируются в порядке возрастания. Пусть PQ - очередь приоритетов. Сначала мы помещаем самый большой элемент в очередь приоритетов. Затем выполните следующее, если PQ не пуст:

• Поп самый большой элемент из PQ
• добавить элемент adajcent выше, если у PQ нет элемента из этой строки
• добавить элемент adajcent слева, если у PQ нет элемента из этого столбца, и если он не находится под диагональю матрицы (чтобы избежать избыточных элементов)

Обратите внимание, что

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

Каждый раз, когда PQ выдает одно и то же значение дважды, мы нашли номер такси.

В качестве иллюстрации здесь представлена ​​реализация на С++. сложность времени - это O (N ^ 2 logN) и пространственная сложность O (N).

#include <iostream>
#include <cassert>
#include <queue>

using namespace std;

typedef unsigned int value_type;

struct Square
{
   value_type i;
   value_type j;
   value_type sum_of_cubes;
   Square(value_type i, value_type j) : i(i), j(j), sum_of_cubes(i*i*i+j*j*j) {}
   friend class SquareCompare;
   bool taxicab(const Square& sq) const
   {
     return sum_of_cubes == sq.sum_of_cubes && i != sq.i && i != sq.j;
   }
   friend ostream& operator<<(ostream& os, const Square& sq);
};

class SquareCompare
{
public:
  bool operator()(const Square& a, const Square& b)
  {
    return a.sum_of_cubes < b.sum_of_cubes;
  }
};

ostream& operator<<(ostream& os, const Square& sq)
{
  return os << sq.i << "^3 + " << sq.j << "^3 = " << sq.sum_of_cubes;
}

int main()
{
  const value_type N=2001;
  value_type count = 0;
  bool in_i [N];
  bool in_j [N];

  for (value_type i=0; i<N; i++) {
    in_i[i] = false;
    in_j[i] = false;
  }

  priority_queue<Square, vector<Square>, SquareCompare> p_queue;

  p_queue.push(Square(N-1, N-1));
  in_i[N-1] = true;
  in_j[N-1] = true;

  while(!p_queue.empty()) {
    Square sq = p_queue.top();

    p_queue.pop();
    in_i[sq.i] = false;
    in_j[sq.j] = false;

    // cout << "pop " << sq.i << " " << sq.j << endl;

    if (sq.i > 0 && !in_i[sq.i - 1] && sq.i-1 >= sq.j) {
      p_queue.push(Square(sq.i-1, sq.j));
      in_i[sq.i-1] = true;
      in_j[sq.j] = true;
      // cout << "push " << sq.i-1 << " " << sq.j << endl;
    }
    if (sq.j > 0 && !in_j[sq.j-1] && sq.i >= sq.j - 1) {
      p_queue.push(Square(sq.i, sq.j-1));
      in_i[sq.i] = true;
      in_j[sq.j - 1] = true;
      // cout << "push " << sq.i << " " << sq.j-1 << endl;
    }

    if (sq.taxicab(p_queue.top())) {
      /* taxicab number */
      cout << sq << " " << p_queue.top() << endl;
      count++;
    }
  }
  cout << endl;

  cout << "there are " << count << " taxicab numbers with a, b, c, d < " << N << endl;

  return 0;
}

Ответ 3

Ответы Novneet Nov и user3017842 являются правильными идеями для поиска номеров такси с хранением O (N) с использованием minHeap. Просто немного больше объяснений, почему работает minHeap размера N. Во-первых, если бы у вас были все суммы (O (N ^ 2)) и они могли сортировать их (O (N ^ 2lgN)), вы просто выбираете дубликаты при перемещении отсортированного массива. Ну, в нашем случае с помощью minHeap мы можем пройти по всем суммам: просто нужно убедиться, что minHeap всегда содержит минимальную необработанную сумму.

Теперь у нас есть огромное количество сумм (O (N ^ 2)). Но заметьте, что это число можно разбить на N групп, каждый из которых имеет легко определенный минимум! (fix a, изменить b из 0 to N-1 = > вот ваши группы N. Сумма в одной группе с меньшим b меньше единицы с большим b в той же группе - потому что a то же самое).

Минимум объединения этих групп заключается в объединении mins этих групп. Поэтому, если вы сохраняете все минимумы этих групп в minHeap, вы гарантированно получите общий минимум в minHeap.

Теперь, когда вы извлекаете Min из кучи, вы просто добавляете следующий наименьший элемент из группы этого извлеченного min (поэтому, если вы извлекли (a, b), вы добавили (a, b+1)), и вам гарантировано, что ваш minHeap все еще содержит следующий необработанный минимум всех сумм.

Ответ 4

Я нашел решение/код здесь: Сложность времени O (N ^ 2 logN), сложность пространства O (N) Решение реализуется с помощью очередей приоритетов.

Обратное мышление можно легко сделать, посмотрев на код. Это можно сделать в массиве размером N, потому что минимальные суммы удаляются из массива после сравнения с следующим минимумом, а затем массив делается для размера N, добавляя новую сумму - (i ^ 3 + (j + 1) ^ 3).

Интуитивное доказательство здесь:

Вначале мы добавили (1,1), (2,2), (3,3),..., (N, N) в очередь с минимальным приоритетом.

Предположим, что a ^ +b ^ 3 = c ^ 3+ d ^ 3, и (a, b) - это минимум, который будет выведен из следующей очереди приоритетов. Чтобы определить этот номер такси, (c, d) также должен быть в очереди приоритетов, которая будет выведена после (a, b).

Примечание. Мы добавляем (a, b + 1) после извлечения (a, b), поэтому нет способа, чтобы извлечение (a, b) приводило к добавлению (c, d) в очередь приоритетов, поэтому оно должен существовать в очереди приоритетов.

Теперь давайте предположим, что (c, d) не находится в очереди приоритетов, потому что мы еще не дошли до него. Вместо этого в очереди приоритетов есть (c, d-k), где k> 0.

Так как (a, b) вынимается, a ^ 3 +b ^ 3≤c ^ 3+ (d-k) ^ 3

Однако a ^ 3 +b ^ 3 = c ^ 3+ d ^ 3

Следовательно,

c ^ 3+ d ^ 3≤c ^ 3+ (d-k) ^ 3 d≤d-k k≤0

Так как k> 0, это невозможно. Таким образом, наше предположение никогда не может произойти. Таким образом, для каждого (a, b), который удаляется из min-PQ, (c, d) уже находится в min-PQ (или просто удаляется), если a ^ 3 +b ^ 3 = c ^ [CN10 ] д ^ 3

Ответ 5

• создать массив: 1 ^ 3, 2 ^ 3, 3 ^ 3, 4 ^ 3,....... k ^ 3. такой, что k ^ 3 < N и (k + 1) ^ 3 > N. размер массива будет ~ (N) ^ (1/3). массив отсортирован по порядку.
• используйте метод 2sum (ссылка) в линейном времени, пропорциональном размеру массива. если мы найдем две пары чисел, то есть хит.
• проходя через шаг 2, каждый раз уменьшая N на 1.

Это будет использовать дополнительное пространство O (N ^ (1/3)) и ~ O (N ^ (4/3)).

Ответ 6

Простой способ понять Сложность времени O (N ^ 2 logN), сложность пространства O (N) - считать ее слиянием из N отсортированных массивов плюс бухгалтерия ранее объединенного элемента.

Ответ 7

version1 использует список и сортировку
O (n ^ 2 * logn) время и O (n ^ 2) пространство

    public static void Taxicab1(int n)
    {
        // O(n^2) time and O(n^2) space
        var list = new List<int>();
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j <= n; j++)
            {
                list.Add(i * i * i + j * j * j);
            }
        }

        // O(n^2*log(n^2)) time
        list.Sort();

        // O(n^2) time
        int prev = -1;
        foreach (var next in list)
        {
            if (prev == next)
            {
                Console.WriteLine(prev);
            }
            prev = next;
        }
    }

version2 использует HashSet
O (n ^ 2) время и O (n ^ 2) пространство

    public static void Taxicab2(int n)
    {
        // O(n^2) time and O(n^2) space
        var set = new HashSet<int>();
        for (int i = 1; i <= n; i++)
        {
            for (int j = i; j <= n; j++)
            {
                int x = i * i * i + j * j * j;
                if (!set.Add(x))
                {
                    Console.WriteLine(x);
                }
            }
        }
    }

version3 использует min ориентированный Priority Queue
O (n ^ 2 * logn) и O (n) пространство

    public static void Taxicab3(int n)
    {
        // O(n) time and O(n) space
        var pq = new MinPQ<SumOfCubes>();
        for (int i = 1; i <= n; i++)
        {
            pq.Push(new SumOfCubes(i, i));
        }

        // O(n^2*logn) time
        var sentinel = new SumOfCubes(0, 0);
        while (pq.Count > 0)
        {
            var current = pq.Pop();

            if (current.Result == sentinel.Result)
                Console.WriteLine($"{sentinel.A}^3+{sentinel.B}^3 = {current.A}^3+{current.B}^3 = {current.Result}");

            if (current.B <= n)
                pq.Push(new SumOfCubes(current.A, current.B + 1));

            sentinel = current;
        }
    }

где SummOfCubes

public class SumOfCubes : IComparable<SumOfCubes>
{
    public int A { get; private set; }
    public int B { get; private set; }
    public int Result { get; private set; }

    public SumOfCubes(int a, int b)
    {
        A = a;
        B = b;
        Result = a * a * a + b * b * b;
    }

    public int CompareTo(SumOfCubes other)
    {
        return Result.CompareTo(other.Result);
    }
}

github

Ответ 8

Кажется, что простой алгоритм грубой силы с правильными оценками решает его во времени, пропорциональном п ^ 1.33 и пространству, пропорциональному п. Или кто-нибудь может указать мне на место, где я ошибаюсь?

Рассмотрим 4 вложенных цикла, каждый из которых работает от 1 до кубического корня из n. Используя эти циклы, мы можем использовать все возможные комбинации из 4 значений и находить пары, образующие номера такси. Это означает, что каждый цикл занимает время, пропорциональное кубическому корню из n, или n ^ (1/3). Умножьте это значение 4 раза и получите:

(n^(1/3)^4 = n^(4/3) = n^1.33

Я написал решение в JavaScript и проверил его, и, похоже, он работает. Одно из предостережений состоит в том, что результат частично сортируется.

Вот мой код JavaScript (он еще не оптимален, можно оптимизировать еще больше):

function taxicab(n) {
  let a = 1, b = 1, c = 1, d = 1,
  cubeA = a**3 + b**3,
  cubeB = c**3 + d**3,
  results = [];

  while (cubeA < n) { // loop over a
    while (cubeA < n) { // loop over b
      // avoid running nested loops if this number is already in results
      if (results.indexOf(cubeA) === -1) {
       while (cubeB <= cubeA) { // loop over c
        while (cubeB <= cubeA) { // loop over d
          if (cubeB === cubeA && a!=c && a!=d) { // found a taxicab number!
            results.push(cubeA);
          }
          d++;
          cubeB = c**3 + d**3;
        } // end loop over d
        c++;
        d = c;
        cubeB = c**3 + d**3;
       } // end loop over c
      }
      b++;
      cubeA = a**3 + b**3;
      c = d = 1;
      cubeB = c**3 + d**3;
    } // end loop over d
    a++;
    b = a;
    cubeA = a**3 + b**3;
  } // end loop over a

  return results;
}

Запуск taxicab(1E8) занимает около 30 секунд в консоли браузера и дает в результате 485 номеров. Десятикратная меньшая стоимость taxicab(1E7) (10 миллионов) занимает почти 1,4 секунды и дает 150 номеров. 10^1.33 * 1.4 = 29.9, т.е. Умножение n на 10 приводит к увеличению времени работы на 10 ~ 1,33 раза. Массив результатов несортирован, но после быстрой сортировки мы получаем правильный результат, как кажется:

[1729, 4104, 13832, 20683, 32832, 39312, 40033, 46683, 64232, 65728,
110656, 110808, 134379, 149389, 165464, 171288, 195841, 216027, 216125,
262656, 314496, 320264, 327763, 373464, 402597, 439101, 443889, 513000, 
513856, 515375, 525824, 558441, 593047, 684019, 704977, 805688, 842751, 
885248, 886464, 920673, 955016, 984067, 994688, 1009736, 1016496, 1061424,
1073375, 1075032, 1080891, 1092728, 1195112, 1260441, 1323712, 1331064,
1370304, 1407672, 1533357, 1566728, 1609272, 1728216, 1729000, 1734264,
1774656, 1845649, 2048391, 2101248, 2301299, 2418271, 2515968, 2562112,
2585375, 2622104, 2691451, 2864288, 2987712, 2991816, 3220776, 3242197,
3375001, 3375008, 3511872, 3512808, 3551112, 3587409, 3628233, 3798613,
3813992, 4033503, 4104000, 4110848, 4123000, 4174281, 4206592, 4342914,
4467528, 4505949, 4511808, 4607064, 4624776, 4673088, …]

Вот код для бенчмаркинга:

// run taxicab(n) for k trials and return the average running time
function benchmark(n, k) {
  let t = 0;
  k = k || 1; // how many times to repeat the trial to get an averaged result

  for(let i = 0; i < k; i++) {
    let t1 = new Date();
    taxicab(n);
    let t2 = new Date();
    t += t2 - t1;
  }
  return Math.round(t/k);
}

Наконец, я протестировал его:

let T = benchmark(1E7, 3); // 1376 - running time for n = 10 million
let T2 = benchmark(2E7, 3);// 4821 - running time for n = 20 million
let powerLaw = Math.log2(T2/T); // 1.3206693816701993

Таким образом, это время пропорционально n ^ 1,32 в этом тесте. Повторение этого много раз с разными значениями всегда дает примерно тот же результат: от 1,3 до 1,4.