К сожалению последние 2 месяца были физические ограничения по работе с компом. Сейчас ситуация улучшается, надеюсь дальше таких больших пауз не будет. Следующее видео почти готово и будет в понедельник или вторник. Спасибо за поддержку :).
И еще, знающие люди, подскажите, почему коэффициент предпочтительнее <0.7? Если по примеру из книги, то на 100 квартир должны быть 70 котиков, смысл оставлять пустым квартиры?))
Как я понял 0,7 взято просто из практики, опытным путем. Главная цель соблюдение баланса между: с одной стороны затратами на памяти и с другой - издержками, которые приносят тормоза при большом количестве коллизий, тут ещё есть, где-то затраты на создание хеш-функции. Если коэффициент меньше то память расходуется сильно впустую, если больше - рост коллизий - соответственно рост тормозов в работе. В вопросе с котиками и квартирами, затраты на квартиры (на память) огромные, и первая мысль которая мне пришла: действительно коэффициент 0,7 очень неэффективен. Вторая мысль: а если поселить котиков в обувные коробки. Ну 100 коробок уже не жалко, да хоть 150 :))) Спасибо за вопрос, ради таких вопросов и стоит выкладывать видео. PS: Сделаю программку, что бы раскидать случайным образом 50, 60, 70, 80, 90 шаров по 100 ячейкам. Посмотреть долю пустых ячеек и кол-во коллизий в каждом случаях, может получим ответ.
Искренне не понимаю, почему тут так мало лайков! В видео отличное объяснение, помогает вспомнить материал или же сначала посмотреть видео, а потом и книжку почитать)
Вы имеете ввиду в коде примера? Так как имя функции не является ключевым словом, можно любое имя придумать, я написал через k это по-немецки, но Вы правы! лучше в именах переменных и функций использовать английские слова, поэтому понятнее было бы function. постараюсь в будущем на это обращать внимание. Спасибо за внимательность.
Посмотрел сейчас быструю сортировку у Алекс ОС, не понял, что можно было подумать, что я там повторил, мне до его визуала расти и расти ещё. Так что сообщение воспринимаю не иначе, как комплимент. Спасибо.
Добрый день, классно объясняете! Но есть вопрос 5:51: со связными списками при вставке\удалении понятно: дойти до позиции О(n-1), вставить или удалить О(1), итог - n-1+1 = n. Но почему у массивов О(n) + О(1) = О(n)? А не О(n+1)? 1 - это константа и она игнорируется?
Добрый день. Спасибо! Ваш вопрос в очень в правильном месте. Посмотрел видео в этой части и увидел свою ошибку. Касаемо связанных списков: для того, что бы дойти до позиции нужно все же потратить максимально n шагов, а не n-1. И в этом ошибка в видео. Т.е. в сумме О большое для связанных списков так же, как и для массивов равно n+1. В этом месте в книге логика размышления автора была очень не понятна, по крайней мере для меня и ещё пары человек. Что самое интересное, когда я делал видео, я так и не понял, что автор имел ввиду, поэтому пришлось этот кусок брать из других источников. Сейчас же после вашего вопроса, посмотрел своё видео, открыл книгу и сразу понял😊 Автор под вставкой имел ввиду отдельную операцию вставки, т.е. как будто адрес ячейки уже в наличии. Т.е. он разделяет операцию чтения и вставки, и дает для каждой операции О большое в отдельности, но об этом не говорит. Поэтому у него получается скорость чтения связанных списков О(n) скорость вставки O(1). Я рассуждал с позиции вставка без чтения невозможна, поэтому никак не мог понять почему у него вставка в связанный список занимает только один шаг. Благодаря вашему вопросу, вернулся к теме вновь и понял автора, спасибо!😊 Итого: вставка и удаление, как цельная операция, как для массивов так и для связанных списков в сумме будет иметь одинаковое значение О(n+1). По факту вы сами ответили на свой вопрос. 😊 Константы в О большом игнорируются, так как при огромном n они становятся не заметны, да и О большое так же интересно в динамике, т.е. как изменяется количество шагов при изменении количества элементов. Например: у нас О большое О(n+2). При изменении n с 100 до 200 потом до 300, количество шагов меняется с 102 до 202 потом до 302, линейно, с той же скоростью, смысла нет держать такую константу и О большое записывается без константы, как O(n). Бывает ещё одна константа, когда зависимости можно описать так: О(c*n) - она тоже игнорируется. Так как если мы будем сравнивать О(c*n) и О(d*logn) то даже если с на порядки больше d при больших n алгоритм с О(d*logn) будет быстрее. Но вот если сравнивать два алгоритма с одинаковым О-большим - такую константу я думаю следует учитывать. Чисто гипотетически например: О(n) и О(c*n) при с = 0,5. При любом n второй алгоритм быстрее первого. Но тут так же в обоих случаях нотация О-большое будет записана как О(n)
Есть два издания, 4ое и 5ое. Отличие только в последней главе, ну и в 5ом есть ещё про f-строки, про них в ролике 2ой главы. На данный момент, где точно взять не подскажу, но для погружения в тему подойдет любое издание. Полное название книги звучит так: Начинаем программировать на Python. автор: Тони Гэддис.
