J
задачка с codewars. там вот некоторые пользователи сделали через линкедлист со сложностью O(N) вроде
вот как
Size: a a a
2021 January 07
K
задачка с codewars. там вот некоторые пользователи сделали через линкедлист со сложностью O(N) вроде
изи
MP
привет, если кто разбирается, можете подсказать какая временная сложность моего алгоритма? https://pastebin.com/E83kkzXS
Сложность скорее всего будет n log (n). Так как у вас две сортировки. Проход сравнения можно не учитывать, так как его сложность просто n. Как вариант - запихнуть одно слово в hashmap и за один проход проверить наличие букв в нем (и удалить)
K
проходите по кажой букве s2 и смотрите есть ли данная буква в s1. если нет хотя бы 1 буквы вы выдаете false
K
O(n)
dd
привет, если кто разбирается, можете подсказать какая временная сложность моего алгоритма? https://pastebin.com/E83kkzXS
Сначала О(n*log(n)) , где n это максимально длинная из строк, потом цикл О(n*m).
Итоговая сложность О(n*m).
А вообще рекомендую переписать без использования меток
Итоговая сложность О(n*m).
А вообще рекомендую переписать без использования меток
MP
Скорее всего это n^2. Так как каждый раз пробегать по линкед лист. И как завещал Тагир - н используйте нигде linked list
J
проходите по кажой букве s2 и смотрите есть ли данная буква в s1. если нет хотя бы 1 буквы вы выдаете false
но тогда если будет слово str2 = hello то выдаст true для srt1= helooo например
dd
может по новее что нибудь найти, там еще аплеты упоминаются
Курс устарел, но ничего нового столь-же толкового я не знаю
ДБ
ну вот уже слушаю, столько воды... есть что посоветуете новичку в постижении?
Там нет воды.
J
Скорее всего это n^2. Так как каждый раз пробегать по линкед лист. И как завещал Тагир - н используйте нигде linked list
n^2 это много, как мне кажется. добавление в линкедлист и удаление это O(N) плюс проход for по str2 (это тоже вроде будет O(N)
K
не если по брутфорсу то можно создать dict для каждого слова и уже сравнивать их
J
хотя это O(N) внутри O(N)... сложно. нужно почитать литературу об этом а то предполагать надоело
p
хотя это O(N) внутри O(N)... сложно. нужно почитать литературу об этом а то предполагать надоело
посоветуйте что гуглить чтобы почитать про O(N) N(0) и вот это все..
K
посоветуйте что гуглить чтобы почитать про O(N) N(0) и вот это все..
time complexity в youtube
p
time complexity в youtube
пасиба
K
space complexity тоже не забыть
ДБ
2 сета и проверить contains не пойдет?
K
2 сета и проверить contains не пойдет?
Неа
ДБ
Почему?