Константа во всем: одна простая задача за O(1)

O-нотация - это всего лишь оценка функции сверху. Если среднее время работы avg_time = f(n) = const, то формально avg_time = O(1). Где здесь манипуляция?

В таком случае хеш-таблицы вам тоже должны не нравиться: там время вставки O(1) — это именно среднее время, а не оценка в худшем случае.

Константа во всем: одна простая задача за O(1)

Спасибо за комментарий и ссылки на теоремы!

Константа во всем: одна простая задача за O(1)

Рандом вообще не причем тут, они ведь уже перемешаны по условию

Где такое можно прочитать?)

Наоборот, если мы говорим про олимпиадное программирование, где все тесты запускаются независимо, то опытные составители обязательно подсунут вам тесты, на которых без рандома все будет работать медленно.

Мы точно решаем или неточно.

Мне кажется, вы путаете два разных понятия: приближенные и рандомизированные алгоритмы. Первые - выдают ответ с определенной погрешностью. Вторые - просто используют внутри себя рандом (как например quick sort).

Константа во всем: одна простая задача за O(1)

Шикарное решение, спасибо!

Константа во всем: одна простая задача за O(1)

Да, именно так :)

Решение авторов именно такое.

Константа во всем: одна простая задача за O(1)

O(1) по памяти, а не по времени.

Константа во всем: одна простая задача за O(1)

Если массив на вход подается случайный, то метод random ничего нового не привносит. Разумеется, он только замедлит. Однако, на плохих входах будет деградация до O(N).

Константа во всем: одна простая задача за O(1)

Если массив был случайно перемешан, да. Однако, если нам назло подсунули плохой массив, будет O(n), например:

[1, 2, 3, ..., 1000, 1, 1, 1, ..., 1]

Решение за O(1) по памяти без рандома здесь: https://youtu.be/B-1h5xEjBvk?si=RVxUnYKOJnnx-wZK&t=791

Черепаха в лабиринте: Медлительное путешествие к свободе

Да я уже нашел ошибку в статье, так что этот вопрос уже закрыт.

Благодарю вас за проделанную работу. Однако, ни на одну фактическую ошибку вы так и не указали, зато сообщили всем вокруг, что не смогли ничего понять.

Убедительно прошу прекратить вас спамить и замусоривать комментарии.

Спасибо!

В поисках алгоритмического дзена

Имея на руках две реализации можем посмотреть как они себя поведут в бенчмарке (Length - кратное увеличение размера строки, чтобы смотреть как ведет себя реализация на больших данных)

Из статьи не совсем ясно, что такое "большие данные". Нет ни слова о том, как вы их на самом деле генерируете, а это может существенно влиять на бенчмарки.

Если я верно понял, вы просто много раз повторяете исходную строку? В таком случае, это не совсем честный бенчмарк, т.к. максимум достигается почти сразу (на первом же вхождении исходной строки в длинную). Интереснее было бы посмотреть на тест, в котором максимум постоянно растет.

В поисках алгоритмического дзена

del

В поисках алгоритмического дзена

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

Получается, если я захочу воспроизвести ваши результаты на своем компьютере и измерить время работы у себя, у меня не получится это сделать? В чем смысл тогда вообще код приводить, если вы знаете, что он работать не будет?

Сниппет — это блок с краткой информацией о странице сайта, содержащий ссылку на документ, который отображается в результатах поиска.

Сниппет - это просто англицизм от англ. snippet - фрагмент, отрывок. Тем более, смысл был из контекста понятен.

В поисках алгоритмического дзена

У вас во втором сниппете кода баг. Сможете найти?

// SkipWord
int maxlen = 1;
int maxindex = -1;
int temp_maxlen = 0;
int temp_maxindex = 0;
int i = 0;
while (i < str.Length)
{
    if ((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z'))
    {
        temp_maxlen = 0;
        temp_maxindex = i;
        do
        {
            temp_maxlen++;
            i++;
        }
        while (((str[i] >= 'a' && str[i] <= 'z') || (str[i] >= 'A' && str[i] <= 'Z')) && i < str.Length);
        if (temp_maxlen > maxlen)
        {
            maxlen = temp_maxlen;
            maxindex = temp_maxindex;
        }
    }
    i++;
}
Console.WriteLine("Длина = {0}, слово = {1}", maxlen, str.Substring(maxindex, maxlen));

Черепаха в лабиринте: Медлительное путешествие к свободе

о том и речь, нет алгоритма и нет реализации, есть идея

Вполне корректный алгоритм.

небрежно оформленная, вы даже псевдокод написали умолчав о половине действий

А код на питоне вас устроит? :)

Черепаха в лабиринте: Медлительное путешествие к свободе

Браво! А теперь замените черепаху на синюю клетку и получится дословно алгоритм из статьи.

1. Создать список синих клеток (все свободные клетки лабиринта)

2. Цикл - пока список синих клеток не пуст

3. Рассчитать путь для синей клетки до выхода

4. Записать в результирующий список команд

5. Передвинуть все синие клетки из списка по маршруту из п.3 производя слияние элементов списка при совпадении клеток или удаляя из списка тех, что вышли из лабиринта

6. Вернуться в п.2

Черепаха в лабиринте: Медлительное путешествие к свободе

а причем здесь задача? я пишу о реализации своего алгоритма на ЯП, вы за контекстом треда следите.

Так если задача не причем, почему пишите об этом здесь?

Черепаха в лабиринте: Медлительное путешествие к свободе

Где некая оптимизация, отчего-то же автор даже статью написал

Оптимизация чего? Я как автор статьи не совсем понимаю, о чем вы :)

Черепаха в лабиринте: Медлительное путешествие к свободе

мне не требуется Дейкстра чтобы найти выход, информация о том как именно выйти строится во время обхода.

Да нет никакой разницы как вы его найдете, хоть dfs запустите. Речь же не о том. Задача стояла "придумайте алгоритм, который выпишет конечную последовательность". Это теоретическая задача, а не контест. Здесь никаких ограничений по времени и памяти нет у вас нет.

Черепаха в лабиринте: Медлительное путешествие к свободе

Зачем мне выбирать клетку без черепахи?

Затем, что вы не знаете, где черепаха. Все синие клетки для вас норм.

Мне кажется вы уже просто меня троллите.

Кто кого троллит)

Нет. Например справа от выхода стена, тогда команда "налево" не приведет к тому, что у вас кто-то достигнет финиша.

Одна итерация - это не одна команда, а последовательность команд, переводящая одну из синих клеток в зеленую.

Черепаха в лабиринте: Медлительное путешествие к свободе

То, что выбрав любую точку можно дойти до выхода доказывать как раз не нужно, т.к. это следует из словосочетания "связный лабиринт" :)