A>Резюме: использование хешированного списка (например, Dictionary в C#) является решением задачи за время O(N) и доп. память O(N).
не понимаю. Если сделать хэш размером N, то коллизии хэшей убьют O(1) доступ, и реально будет тот же логарифм.
Чтобы сохранить O(1) (в среднем) доступ нужен хэш размером N*lgN, опять таки вылазит логарифм.
X>Да все я понял, под сравнениями я имел ввиду >, <, <=, >=. Я просто решил задачу в пятницу, захожу сюда, чтобы отписаться вчера, а тут вы решение уже сказали, обидно блин. Такое ощущение, что не сам догадался.
Та ладно.. Фигня все это. Развлекаемся.
Здравствуйте, dilmah, Вы писали:
D>тебе нужно проинициализировать нулями массив размером M. Формально это O(M), если забыть о трюках с paged memory management
Формально да. Есть языки, которые не требуют инициализации.. А так ты прав
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Странно, что никто не предложил такой вариант: lexical sort (=O(N*log(M))) + ещё один проход для сравнения соседних элементов (=O(N)).
Курица — это инструмент, с помощью которого одно яйцо производит другие.
Здравствуйте, frogkiller, Вы писали:
F>Здравствуйте, Xobotik, Вы писали:
F>Странно, что никто не предложил такой вариант: lexical sort (=O(N*log(M))) + ещё один проход для сравнения соседних элементов (=O(N)).
Что-то я не понял откуда в lexical sort оценка O(N*log(M))
radix sort для Int32 займет O(4*N). Т.е. формально за O(N) с дополнительной памятью O(C).
S>Что-то я не понял откуда в lexical sort оценка O(N*log(M))
S>radix sort для Int32 займет O(4*N). Т.е. формально за O(N) с дополнительной памятью O(C).
ну вот эта четверка это и есть log(M) -- другими словами -- количество бит в сортируемых числах
Здравствуйте, andy1618, Вы писали:
A>Здравствуйте, andy1618, Вы писали:
A>>В C# это называется Dictionary<T>. Если правильно указать ёмкость словарика при инициализации (M), то алгоритм будет работать за время O(N). Но есть один нюанс — отожрётся памяти O(M), что в подобных задачах обычно считается неприемлемым (ибо тогда это эквивалентно заведению простого вспомогательного массива из M элементов, после чего задача становится тривиальной).
A>Упс, ошибся! Ведь M может быть очень велико и существенно превышать N (например, M=2^64, N=1000), а для шустрой работы хешированного словарика вполне достаточно памяти порядка O(N). A>Резюме: использование хешированного списка (например, Dictionary в C#) является решением задачи за время O(N) и доп. память O(N).
Да вы правы Словари решают задачу за O(N)
public int GetDuplicateNumber(int[] array)
{
Dictionary<int, int> dictionary = new Dictionary<int, int>(array.Length);
foreach (int i in array) // O(N)
{
if (dictionary.ContainsKey(i)) // Этот метод является операцией порядка сложности O(1)
{
return i;
}
else
{
dictionary.Add(i, 0); // O(1) размер словаря, равен размеру массива, размер не увеличивается
}
}
return 0;
// результат: O(N*1*1) = O(N)
}
Здравствуйте, dilmah, Вы писали:
A>>Резюме: использование хешированного списка (например, Dictionary в C#) является решением задачи за время O(N) и доп. память O(N).
D>не понимаю. Если сделать хэш размером N, то коллизии хэшей убьют O(1) доступ, и реально будет тот же логарифм. D>Чтобы сохранить O(1) (в среднем) доступ нужен хэш размером N*lgN, опять таки вылазит логарифм.
Я так долго копил баллы, за что -1 то? Я метод делал строго по документации MSDN.
D>>не понимаю. Если сделать хэш размером N, то коллизии хэшей убьют O(1) доступ, и реально будет тот же логарифм.
DR>Не будет, посчитай. К тому же, хэш можно сделать размером kN для любого положительного k.
ок, согласен, посчитал количество коллизий стремится к распределению пуассона, так что в среднем константный оверхед.
Но все равно, зависимость от M спрятана неявно -- в вычислении хэша.
X> public int GetDuplicateNumber(int[] array)
X> {
X> Dictionary<int, int> dictionary = new Dictionary<int, int>(array.Length);
X> foreach (int i in array) // O(N)
X> {
X> if (dictionary.ContainsKey(i)) // Этот метод является операцией порядка сложности O(1)
X> {
X> return i;
X> }
X> else
X> {
X> dictionary.Add(i, 0); // O(1) размер словаря, равен размеру массива, размер не увеличивается
X> }
X> }
X> return 0;
X> // результат: O(N*1*1) = O(N)
X> }
X>
а вот так:
public int GetDuplicateNumber(int[] array)
{
Dictionary<int, int> dictionary = new Dictionary<int, int>(array.Length);
for (int i = 0; i < array.Length; i++)
{
if (dictionary.ContainsKey(array[i]))
{
return array[i];
}
else
{
dictionary.Add(array[i], i); // ключи словаря - это значения массива, а значения словаря - это шаг цикла for
}
}
return 0;
}
D>>Но все равно, зависимость от M спрятана неявно -- в вычислении хэша.
S>Можно развернуть мысль?
ну в исходной задаче было озвучено 2 параметра: N и M.
Решение с хэшом имеет сложность O(N) только в предположении, что M не превышает некого фиксированного числа, скажем UINT64_MAX
Но так как M тоже является параметром, то формально сложность равна O(N*log(M)), потому что чем больше M, тем больше бит в числах.
X> public int GetDuplicateNumber(int[] array)
X> { ...
X> dictionary.Add(array[i], i); // ключи словаря - это значения массива, а значения словаря - это
X> ...
X> }
X>
Раз уж начали использовать готовые контейнеры, осталось понять, зачем запоминать в словарь помимо ключа еще и значение (в данном случае i), которое в дальнейшем не используется.
Ведь это:
1. Запутывает код.
2. Увеличивает требования к памяти.
Здравствуйте, Буравчик, Вы писали:
Б>Раз уж начали использовать готовые контейнеры, осталось понять, зачем запоминать в словарь помимо ключа еще и значение (в данном случае i), которое в дальнейшем не используется.
Это да. Вообще говоря, решение через стандартные хеш-словари не очень интересное, любопытно было бы найти какой-то изящный алгоритм. Например, если бы задача звучала "Все числа повторяются по 2 раза, кроме искомого", то обычный побитовый XOR решал бы задачу за O(N) вообще без дополнительной памяти.
Здравствуйте, Буравчик, Вы писали:
Б>Здравствуйте, Xobotik, Вы писали:
X>>
X>> public int GetDuplicateNumber(int[] array)
X>> { ...
X>> dictionary.Add(array[i], i); // ключи словаря - это значения массива, а значения словаря - это
X>> ...
X>> }
X>>
Б>Раз уж начали использовать готовые контейнеры, осталось понять, зачем запоминать в словарь помимо ключа еще и значение (в данном случае i), которое в дальнейшем не используется.
Я заполняю значениями для того, чтобы снизить вероятность коллизии. Значения получаются все разные, тем самым хэши значений тоже разные и из-за этого снижается вероятность коллизии.
Б>Ведь это: Б>1. Запутывает код.
Здравствуйте, andy1618, Вы писали:
A>Здравствуйте, Буравчик, Вы писали:
Б>>Раз уж начали использовать готовые контейнеры, осталось понять, зачем запоминать в словарь помимо ключа еще и значение (в данном случае i), которое в дальнейшем не используется.
A>Это да. Вообще говоря, решение через стандартные хеш-словари не очень интересное, любопытно было бы найти какой-то изящный алгоритм. Например, если бы задача звучала "Все числа повторяются по 2 раза, кроме искомого", то обычный побитовый XOR решал бы задачу за O(N) вообще без дополнительной памяти.
Да задачу (стартовую) решили уже без применения каких-то сложных структур:
Здравствуйте, Xobotik, Вы писали:
X>Условие задачи: X>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>число в этом массиве повторяется два раза. Найти это число за время O(N).
Весь топик не читал, боясь встретить подсказки, а связи нейронные наростить надо бы, ибо вчера была кушал водку
Правиьно ли я понимаю, что только указанного условия достаточно для решения? То есть
порядок N и M может быть достаточно большим
в массиве вовсе не обязательно присутствуют все 1..M, и, как следсnвие, неизвестно, что больше — N или M, то есть M может быть 10^9, а массив [1, 2, 3, 2]
только одно число повторяется (обязательно повторяется) и строго два раза
?
Help will always be given at Hogwarts to those who ask for it.
Здравствуйте, andy1618, Вы писали:
A>Здравствуйте, Буравчик, Вы писали:
Б>>Раз уж начали использовать готовые контейнеры, осталось понять, зачем запоминать в словарь помимо ключа еще и значение (в данном случае i), которое в дальнейшем не используется.
A>Это да. Вообще говоря, решение через стандартные хеш-словари не очень интересное, любопытно было бы найти какой-то изящный алгоритм. Например, если бы задача звучала "Все числа повторяются по 2 раза, кроме искомого", то обычный побитовый XOR решал бы задачу за O(N) вообще без дополнительной памяти.
Да задачу (стартовую) решили уже без применения каких-то сложных структур:
private static int foo(int[] a)
{
int[] b = new int[a.Length];
for (int i = 0; i < a.Length; i++)
{
if (b[a[i]] == 0)
{
b[a[i]] = a[i];
}
else
{
return a[i];
}
}
return 0;
}
Теперь просто пытаемся найти еще другие методы решения задачи.
Здравствуйте, _FRED_, Вы писали:
_FR>Здравствуйте, Xobotik, Вы писали:
X>>Условие задачи: X>>Дан массив размера N из целых чисел, принимающих значения от 1 до M, при этом одно X>>число в этом массиве повторяется два раза. Найти это число за время O(N).
_FR>Весь топик не читал, боясь встретить подсказки, а связи нейронные наростить надо бы, ибо вчера была кушал водку
_FR>Правиьно ли я понимаю, что только указанного условия достаточно для решения? То есть _FR>
_FR>порядок N и M может быть достаточно большим _FR>в массиве вовсе не обязательно присутствуют все 1..M, и, как следсnвие, неизвестно, что больше — N или M, то есть M может быть 10^9, а массив [1, 2, 3, 2] _FR>только одно число повторяется (обязательно повторяется) и строго два раза _FR>_FR>?
