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