а про вероятность достижения худшего случая там ничего не говорилось?
), то далее резонно использовать "уникализацию" сортировкой.
Это ключевые слова - "теоретически". Ты представляешь себе, что во время работы алгоритма, он "вдруг" решает, что "чо-то много коллизий". Кладет на проделанную работу ржавый болт с левой резьбой и начанает заниматься сортировкой (сложность которой для общего случая уж никак не меньше O(n log n)).
Переводить тут надеюсь не надо?
отлично представляю, а что?
Если уж hashtable перевалил за (n ln n), то есть риск дальнейшего роста сложности до O(n * n), так что можно проделать всего лишь двойную работу вместо потенциального O(n * n): выкинуть результаты работа хэша и перейти к сортировке.
для среднего _случая_ - http://phpclub.ru/talk/showthread.php?postid=791204#post791204
этот случай нам не грозит, потому что equality-testing в array_unique основан на операторе (string) (если верить документации), а в PHP в (string) можно конвертировать что угодно.
Вот. Так каким образом ведется подсчет того, что алгоритм уже перевалил O(n log n) ? Когда количество итераций превысит n*log(n) ? Или все таки C*n*log(n), где C какой-то коэффициент (вопрос а какой? как выбирается?). Допустим даже, что определили, после чего запускаем сортировку, какова сложность алгоритма получится общая ? O(n*log (n)) с ужасно большим коэффициентом. Но никак не O(n), согласись.
Я не знаю Питона, поэтому можешь мне объяснить какая сложность у этой операции для него в вышеприведенной тобой ссылке?
u[x] = 1Да хотя бы считать кол-во операций хэширования. Если хэш-таблица разрежена и ключи ложатся в основном в пустые позиции, то на вставку N элементов уходит чуть больше N подсчетов хэша-функции. Но если мы видим, что нам при вставке 1000 элементов уже пришлось log10(1000)*1000 = 3000 раз подсчитать хэш-функцию, значит хэш работает неэффективно, и возникает слишком много коллизий. Но эта ситуация с превышением лимита в 3000 будет возникать в 0.000...1% случаев. В остальные 99.999...% будет сложность алгоритма около O(n).
Такая же, как в пхп. Такая же, как любая вставка в хэш-таблицу.
Ессно, в ЛЮБОМ случае они этого гарантировать не могут. Всего лишь в 99.9999...% случаев
А если все последующие элементы будут ложится за O(1)? Это обычная эвристика работает эффективно не во всех случаях.
Как откуда ... мы уже проделали O(n log n) шагов и после этого еще запускаем сортировку, которая тоже займет O(n log n) итераций. И каждый из алгоритмов со своим коэффициентом. Суммарно может получится довольно внушительно.
Думаю дальше продолжать дискуссию не имеет смысла, мы говорим о разных вещах.
А ты посчитай. Например, вероятность получить 100% коллизий (все элементы в одном "букете") для хэш-таблицы из 100 _рандомных_ (не-crafted) элементов = 10^(-98).
)<?php
class A{
public $a = 0;
}
class B extends A{
public $c = 1;
}
$test = new B();
$test2 = new B();
$test->a = 1;
$test2->a = 2;
$result = array_unique(array($test,$test2));
var_dump($result);
?>
-
Catchable fatal error: Object of class B could not be converted to string