Дмитрий, я имел ввиду ассимптотическую сложность по времени. Чем она меньше, тем производительнее код на больших входных данных. Грубо говоря, сложность показывает, как быстро растет время работы при увеличении входных данных.
galaxy, Но так нельзя. Если делать float**, то надо сначала выделить массив из n указателей, а потом для каждой строки отдельно выделять память.
Вы выделили двумерный массив, и преобразовали указатель на первый float элемент в float**. При обращении к a[i][j] тут происходит обращение по адресу, записанному в блоке float-ов.
Никита,
Во-первых, можно соптимизировать код. Вам не нужны на самом деле рекурсивные вызовы. Ведь каждый раз вызов идет только в одну сторону. Надо переписать quicksort с одним циклом while. Вы внутри разбиваете, потом смотрите, в какую сторону нажно идти и меняете переменные. Потом следующая итерация цикла сделает то, что вы хотели сделать вашим рекурсивным вызовом.
Также можно вставить код partition прямо в тело quicksort.
Попробуйте воткнуть в начало srand(ваше-любимое-число). Может жюри подобрали плохой тест. Надо рандомизировать что-то самим. Вмеcто std::swap ручная реализация может быть быстрее.
Но главное, введите тест A=0, B=0, array[0]=array[1]. Все числа в массиве будут одинаковые. Тут ваша реализация будет откусывать по 1 элементу и работать за квадрат.
Можно сделать все числа уникальными, если расширить их до 64-бит, где старшие биты - входные данные, а нижние 32 бита - тупо индекс числа. Найдите тут k-ое число и выведите старшие биты.
Ну, или меняйте ++last с i с некоторой вероятностью, если a[i] == pivot.
Или можно переписать с использованием разбиения Хоара (у вас Ломуто сейчас). Оно на таком вырожденном тесте всегда будет разбивать по середине.
xmoonlight, Очевидный критерий: разбить на n k-или-менее-угольников никогда нельзя (n*k+1)-или-больше-угольник. Потому что все изначальные углы никуда не денутся и по pigeonhole принципу какой-то из n кусков будет более чем k-угольником. Но это если нам так повезет, что мы все границы проводим исключительно хордами и получаем равные по площади куски. Скорее всего придется проводить всякие ломаные да еще и из центров сторон. Поэтому видимо n(k-3) >= количеству вершин в изначальном многоугольнике. Это не обязательное, но, похоже, достаточное условие.
И массив соединений этих точек: [[p1,p2],[p3,p4],.....[pN,p1]]
А [p2, p3]?
Просто по кругу точки замкнуты, же?
Области на которые мы пилим многоугольник - они могут быть как бублики с дрыками? Иметь анклавы? Или обычные человеческие многугольники, хоть и не выпуклые?
Magneto903, Еще варинат есть использовать heap - должно быть сильно быстрее.
Дейкстра работает за O(n^2+m) потому что вам надо n раз искать вершину с минимальным расстоянием ну и вы по каждому ребру ровно один раз посмотрите, улучшает ли оно расстояние до другого конца.
Если минимум искать через хип, то будет O((n+m)log n) операций, что сильно лучше для вашего случая (m < n^2), потому что хип умеет выдавать минимум и изменять значение за log n.
Вы же, кажетcя, ссылку давали на этот сборник алгоритмов.
Там есть heap. Вам надо хранить в хипе пары {расстояние, номер вершины} до всех пока не visited вершин, у которых есть расстояние. Изначально heap пустой совсем.
Вам надо переписать shortestDistanceNode просто брать минимум из minHeap. При изминении distances в цикле по node вам надо добавлять в minHeap новый объект {расстояние, номер вершины}. Именно в таком порядке, чтобы минимальный элемент содержал минимальное расстояние. Ну или функции сравнения переписать.
Но тут ньюанс - в хипе может быть куча копий вершины, ведь вы будете добавлять новую копию каждый раз, когда обновите расстояние. Поэтому еще надо цикл по child пропускать, если вершина из heap уже в visited.
Или вам придется этот minHeap немного переписать, чтобы проддерживать map из номеров вершин в их позиции в хипе. И при каждом изменении массива heapContainer обовлять этот map. Тогда в методе remove не надо будет выполнять линейный поиск через find.
Потом при изменении distance в основном цикле вы должны будете удалить вершину child[0] из хипа перед добовлением ее копии с новым расстоянием.
Magneto903, Нет не надо матрицы смежности, оставьте списки инцидентности. Пусть у вас будет массив списков объектов {конец ребра, цена}. Раньше у вас там был словарь из строк-имен вершин. Но раз мы поменяли на числа, то можно это заменить массивом, который будет быстрее.
Вообще, по идее, если вместо Map использовать массивы ("[]"? Array?) должно еще быстрее быть.
Еще цикл в начале, который проходится по детям startNode - он лишний.
По поводу функции восстановления пути: надо distances[startNode] = 0 делать перед циклом по node. Иначе алгоритм находит путь в эту вершину через какую-то другую. Путь, который начинается в startNode же. В итоге получается цикл, в котором вы и висните.
Magneto903, попробуйте один хеш завести чтобы по вашим вершинам получать эти graphVertex. Сдается мне, что вы когда новую вершину с тем же именем создаете эта библиотека тоже новую вершину создает а не переиспользует старую.
Magneto903, Выглядит правильно.
Видимо, js-боль. Не знаю, попробуйте вместо хэш таблиц использовать тупо массивы. Сделайте, чтобы у вас вершины нумеровались тупо числами от 0 до сколько-их-там. Структуру соседей сделайте массивом-массивов, а не хешами всякими.
Еще, в цикле не надо проверять ```if (child === startNode) {``` можно просто в начале startNode запихать в visited. Это тоже сколько-то ускорит.
Magneto903, Да, в первой реалзации очевидная проблема с visited.
В этой новой реалезации нет того же бага, но все-равно ассимптотика тоже корявая из-за того, что там одна и та же вершина может быть в очереди сколько угодно раз. Да еще и куча выделений памяти и этот массив очереди может сильно вырасти. А главное, операция добавления в очередь там работает за линию, это не куча же а тоже массив. Поэтому в лучшем случае он будет работать в несколько раз медленее, ведь ребер больше чем вершин.
Вообще js явно страдает от отсутствия вменяемых стандартных структур данных.
xmoonlight, Особенность этого варинта в безразмерности. Т.е. если вы растянете все числа так, что любое расстояние между соседними больше года или сожмете все точки в одну микросекунду, разбиение на кластеры будет точно таким же.
Если в вашей задаче это не вяжется, можно вместо просто после сортировки отсечь по какой-то выбранной вами константе.
Никита, Если массив упорядочен по убыванию, то каждая пара чисел даст инверсию. Всего пар n(n-1)/2. В int помещается 2^31. Решаем уравнение n(n-1)/2=2^31. Или n(n-1)=2^32. Для больших чисел можно грубо прикинуть просто взяв корень, получим, что n~2^16=65536. На самом деле ответ где-то между 65536 и 65537, т.е. я на 1 ошибся - для переполнения нужно 65537 упорядоченных по убыванию чисел.
У вас в задаче может быть 100 тысяч чисел, что больше 65 тысяч, поэтому на максимальном тесте ваше решение переполнит счетчик инверсий и выдадет неправильный ответ.
Поменяйте number_of_inversitions на 64-битный тип и должно заработать.
xmoonlight, Можно жадно - не надо даже дихотомии и динамики. Отсортируйте все соседние расстояния и сливайте эти 2 соседних числа в один кластер, считая метрику.
В вашем примере сначала объединим 9.5 и 10 (разность 0.5), потом 8 и 8.7 (0.7), потом 8.7 и 9.5 (0.8), потом 5 и 6 (1). При слиянии смотрите отношение текущего расстояния и следующего и минимум его тут 1/2.
Можно даже не сливать по пути, а просто найти все разности, отсортировать, найти пару с максимальным отношением и запомнить большее. Потом все точки, с расстоянием меньше этого числа - объединить в один кластер за еще один проход.
xmoonlight, максимальное расстояние между соседними берется по всем кластерам. Да, в {8, 8.7, 9.5, 10} расстояние 0.8, но есть же еще {5, 6}. Идея в этой метрике - мы смотрим как близко точки бывают в одном кластере и как близко бывают точке вне кластеров. Эти 2 множества должны быть хорошо разделены - в кластрерах точки рядышком, а сами кластеры далеко друг от друга.
Требование иметь хотя бы 2 точки в кластерах не влияет на подсчет метрики, и его нужно включить в алгоритм. Например, во время динамики вы не смотрите на варианты, когда последний кластер состоит из одной точки - и все.
