Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
|
|
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
Gennadiy Usov Dima T Надо хэш-таблицу писать с предварительной проверкой что уже есть, так будет быстрее. то получается для N чисел Nx(N-1) сравнений. Нет. Поиск в хэш-таблице не требует перебора всех элементов. Хеш-таблица . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.06.2021, 14:18 |
|
||
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
Dima T Нет. Поиск в хэш-таблице не требует перебора всех элементов. Хеш-таблица . Чтобы понять то, что в массиве нет одинаковых элементов, необходимо СРАВНИТЬ каждый элемент массива с каждым. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.06.2021, 16:01 |
|
||
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
Можно построит дерево из цифр. По принципу префиксного кодирования. Radix типа. Там где листики совпадают для нашего числа - дубликат найден. Недостатки - в негативном сценарии (когда нет совпадений) мы зря потратили полезную память и не просто потратили а захватили больше (т.к. древовидные структуры данных занимают служебную инфу (Nodes) с указателями). Насколько много памяти будет потрачено зря - я не могу оценить. Надо просто практически подойти. Опять-же исходя из того что в средней современной тачке есть 8-16 Гигабайт и мы можем всю ее потратить на решение этой задачи. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.06.2021, 16:36 |
|
||
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
Gennadiy Usov Чтобы понять то, что в массиве нет одинаковых элементов, необходимо СРАВНИТЬ каждый элемент массива с каждым. Нет, не с каждым. Причём далеко не с каждым. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.06.2021, 17:57 |
|
||
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakov Gennadiy Usov Чтобы понять то, что в массиве нет одинаковых элементов, необходимо СРАВНИТЬ каждый элемент массива с каждым. Нет, не с каждым. Причём далеко не с каждым. Как найти похожие числа? Сравниваем 1 с другими, затем 2 с другими (без 1), затем 3 с другими (без 1 и 2) и т.д., пока не найдем 9 и 9. То есть, каждый с каждым. Или есть другие алгоритмы? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.06.2021, 18:37 |
|
||
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
1,2,3,4,5,6,7,8,9,9 Сравниваем 1 с 2, потом 2 с 3 и т.д. пока не сравним 9 и 9. Внезапно нам понадобилось в 10 раз меньше сравнений. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.06.2021, 18:52 |
|
||
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
Dimitry Sibiryakov 1,2,3,4,5,6,7,8,9,9 Сравниваем 1 с 2, потом 2 с 3 и т.д. пока не сравним 9 и 9. Внезапно нам понадобилось в 10 раз меньше сравнений. Там может быть много операций. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.06.2021, 19:56 |
|
||
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
Gennadiy Usov Там может быть много операций. Нет, не может. В твоём случае проверки на равенство это хэш-таблица и O(N), то есть ровно одна операция на вставку каждого значения. В случае "дельта-окрестности" это дерево и O(log2(N)*N), то есть очень мало операций на вставку каждого значения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 15.06.2021, 22:15 |
|
||
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
Gennadiy Usov, чтоб понять, что в массиве байте размером 257 элементов, мне не нужно ничего, чтоб утверждать, что в нем есть как минимум 2 одинаковых элемента. и ничего перебирать не нужно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.06.2021, 00:43 |
|
||
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
Gennadiy Usov, а есть оценка средней длины чисел. Чтоб понять тык-скыть масштаб трагедии. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.06.2021, 10:55 |
|
||
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
mayton Gennadiy Usov, а есть оценка средней длины чисел. Чтоб понять тык-скыть масштаб трагедии. сравнить сумму двух членов в левой части уравнения ВТФ (x^n + y^n = (x + a)^n ) со всеми членами множества пар натуральных чисел Рх1, где х - постоянная величина, y < x, а < x, х1 = 2*x. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.06.2021, 13:12 |
|
||
|
Немного о ВТФ
|
|||
|---|---|---|---|
|
#18+
Решил переделать статью в частные случаи ВТФ (варианты), сократил описания, представил пока 2 варианта. https://sci-article.ru/stat.php?i=1629461371 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.08.2021, 08:22 |
|
||
|
|
Start [/forum/topic.php?fid=16&tid=1339636&gotonew=1]: |
0ms |
get settings: |
2ms |
get forum list: |
7ms |
check forum access: |
0ms |
check topic access: |
0ms |
track hit: |
10ms |
get topic data: |
3ms |
get first new msg: |
3ms |
get forum data: |
2ms |
get page messages: |
28ms |
get tp. blocked users: |
0ms |
| others: | 71ms |
| total: | 126ms |
| 0 / 0 |
