Что касается сложности (если используется алгоритм сортировки на основе сравнения)

Question

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

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

пожалуйста, помогите мне понять разницу.....

Спасибо

Answer 1

На мой взгляд, это не является существенным "противоречием" нижней границы, потому что это частный случай (возможный диапазон значений меньше, чем общее количество элементов, фактически это константа, 3), которая может быть используется, чтобы найти алгоритм быстрее, чем O(N*logN), который является нижней границей для общего алгоритма сортировки на основе сравнения (т. е. там, где у вас нет информации о содержании последовательности).

Как правило, в случае, когда N элементов находятся в диапазоне 0..K с K

Answer 2

Связанный Omega(n log n) дает нижнюю оценку для сортировки произвольных элементов на основе сравнения.

Проблема голландского флага - это случай, когда у вас нет произвольных элементов, а есть только три варианта для каждого элемента.

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

Answer 3

Дело в том, что набор голландских флагов не полностью упорядочен. Есть много равных элементов, на самом деле, когда вы подсчитываете разные объекты, это набор (максимум) размера 3.

Omega(n log n) привязка, вероятно, только трудно, когда для объектов a а также b или a<b или же b>a держит (иначе: все объекты различны)

На самом деле, я могу разобраться в O(0)когда все объекты должны быть null,

Предполагая, что есть как минимум два различных объекта, я считаю, что правильная граница Omega(n log m) где n количество объектов и m это количество различных объектов (которые не сортируются равными). Проще говоря, log m количество решений, необходимых для поиска выходного сегмента. В общем случае O(log m)=O(log n), если количество равных объектов мало. В проблеме голландского флага, m=3,

Radix sort использует это по-другому. Он также считается линейным. Тем не менее, это требует log m передает данные, где m это число возможно различных элементов. Так что на самом деле, сортировка Radix также Omega(n log m), где m количество объектов, которые оно может различить.

Answer 4

Проблема голландского флага - это скорее алгоритм разделения.

Это только первый шаг к сортировке. Вы можете использовать его для сортировки (применяя его к разделам снова и снова), но я думаю, что в итоге вы получите Omega (nlogn).

Знание количества различных значений (3 в случае флага) и их значений (синий, белый, красный) является очень редким случаем.

Answer 5

Проблема голландского флага имеет более базовые данные, чем обычная сортировка, она знает, что есть три разных значения, и если вы посмотрите на страницу википедии для алгоритма, то это:

void threeWayPartition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] < low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }
}

На самом деле он не использовал сравнение между элементами, он просто использовал сравнение между нижней / средней / верхней границей и элементами, что не имеет отношения к другим методам сравнения, которые используются в обычной сортировке, вы можете сравнить его с счетной сортировкой.