более идеальное решение в ответах на литкоде - самый быстрый по времени ответ на эту задачу. контент там для эпилога к видео самое то! кто не смотрел рекомендую глянуть...
Не считаю себя программистом, но тоже сразу думал про поиск пары. Но я пайтон не знаю, можно сказать, думал, что есть уже отдельный метод поиска индекса в массиве по значению элемента, тогда и базу создавать не пришлось бы. Понятно, что на примитивном уровне это было бы тоже самое. Задача не сложная, приятно осознавать, что что-то можешь.))
Только для отсортированного массива! На LeetCode для него даже отдельную задачу сделали leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
Потому что дополнительная память не выделяется и идёт работа только с входным массивом. Не создаются новые массивы, например. Переменные тоже считаются за выделение памяти, но обычно они выделяются фиксировано. Допустим я присвою x = 3 y = 4 z = 9 Получается затрат памяти О(3), но О большая "съедает" константу, а значит получается О(1) Дополнено: допустим О(2*n*log(n) + n) тоже будет O(2nlog(n)), потому что n*log(n) растёт быстрее и потом съедаем константу и получаем О(n*log(n))
В оценки эффективности не учитывается память, которую занимают входные данные. Учитывается только память, которая задействуется непосредственно для работы самого алгоритма.
Это из-за устройства хэш-сетов и хэш-таблиц. Доступ к любому элементу там осуществляется по значению хэш-функции для этого элемента. Направление и «лопату» я дал, дальше дело за вами, мой друг🤜🤛
У меня возник вопрос как у начинающего. В цикле был перебор i и num, получается что i будет принимать 2 числа - это сам элемент после перебора enumerate и его индекс? А как тогда индекс элемента из словаря db будет равен i, если i - это 2 числа? А в целом всё остальное понятно и интересно!
Перебор совсем тупой: зачем для j перебирать весь массив? Взял i и j перебираешь от i+1 до конца списка и т.д. и условие i==j уже не нужно. переборов меньше, время меньше
Да, тут можно так оптимизировать, но на сложность по времени это не повлияет, она все равно останется O(n**2). Я решил не писать эту оптимизацию, чтобы не отвлекать от решения со словарем
![Blox Fruits Dragon Rework Update [Full Stream]](http://i.ytimg.com/vi/EqDAp8udhm0/mqdefault.jpg)
Спасибо за задачу! Для меня как начинающего это огромная щедрость!
более идеальное решение в ответах на литкоде - самый быстрый по времени ответ на эту задачу. контент там для эпилога к видео самое то! кто не смотрел рекомендую глянуть...
Не считаю себя программистом, но тоже сразу думал про поиск пары. Но я пайтон не знаю, можно сказать, думал, что есть уже отдельный метод поиска индекса в массиве по значению элемента, тогда и базу создавать не пришлось бы.
Понятно, что на примитивном уровне это было бы тоже самое.
Задача не сложная, приятно осознавать, что что-то можешь.))
Думаю метод указателей тоже отлично подойдёт
Только для отсортированного массива! На LeetCode для него даже отдельную задачу сделали leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
а почему у нас пространственная сложность O(1), а не О(n)? Ведь нам нужно будет всегда n места в памяти (сам входной массив), чтобы решить эту задачу
Потому что дополнительная память не выделяется и идёт работа только с входным массивом. Не создаются новые массивы, например. Переменные тоже считаются за выделение памяти, но обычно они выделяются фиксировано. Допустим я присвою
x = 3
y = 4
z = 9
Получается затрат памяти О(3), но О большая "съедает" константу, а значит получается О(1)
Дополнено: допустим О(2*n*log(n) + n) тоже будет O(2nlog(n)), потому что n*log(n) растёт быстрее и потом съедаем константу и получаем О(n*log(n))
В оценки эффективности не учитывается память, которую занимают входные данные. Учитывается только память, которая задействуется непосредственно для работы самого алгоритма.
а как понять какие операции какую сложность/память имеют? Вот типа фраза "пробивка по базе это константа", а почему так?
Это из-за устройства хэш-сетов и хэш-таблиц. Доступ к любому элементу там осуществляется по значению хэш-функции для этого элемента. Направление и «лопату» я дал, дальше дело за вами, мой друг🤜🤛
Вот тут есть все "расценки" www.bigocheatsheet.com/
У меня возник вопрос как у начинающего. В цикле был перебор i и num, получается что i будет принимать 2 числа - это сам элемент после перебора enumerate и его индекс?
А как тогда индекс элемента из словаря db будет равен i, если i - это 2 числа? А в целом всё остальное понятно и интересно!
Нет, i будет только индексом -- так работает enumerate
Перебор совсем тупой: зачем для j перебирать весь массив? Взял i и j перебираешь от i+1 до конца списка и т.д. и условие i==j уже не нужно. переборов меньше, время меньше
Да, тут можно так оптимизировать, но на сложность по времени это не повлияет, она все равно останется O(n**2). Я решил не писать эту оптимизацию, чтобы не отвлекать от решения со словарем
ну оптимальнее, да, но n^2 все равно никуда не делся,
а, ну выше Глеб и отписал