Добрый день, классно объясняете! Но есть вопрос 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)
можно узнать, сортировка выбором в приведенном примере займет 36 переборов. (8+7+6+5+4+3+2+1). но 8 в степени 2 = 64. разница почти в 2 раза. Этим пренебрегают? или я что-то неправильно понимаю
Да все верно, константы при указании сложности в О большом игнорируются. Цель О большого показать как растет количество операций в заивисимости от роста входных данных. Интересуют прежде большие числа, при которых коэфиициенты уже не играют роли. Проще говоря мы должны сконцентрироваться именно на типе роста: линейный O(n), квадратичный O(n^2), факториальный O(n!) и т.д. Детали не особо интересуют. Так например зная, что рост у нас факториальный (O(n!)), даже если мы будем делить на 100, при больших n нам это не поможет решит задачу. В главе про жадные алгоритмы в качестве такого примера задача коммивояжёра, там при значении n=17 поиск решения требует очень много времени, на столько много, что оно к тому времени уже не нужно. Итог: мы концентрируемся на типе роста, это как с транспортными средствами, когда речь идет о перемещении из точки в А в точку Б: авто быстрее велосипеда, а самолет быстрее машины. Велосипеды тоже разные, но мы обычно не уточняем его точные характеристики, когда сравниваем с машиной. Я это так вижу.
![[MyGap] Digital Autism: How the Phone Affects the Brain](/img/1.gif)
Неплохо!
Про массивы не знал кстати
Спасибо за коммент:)
Добрый день, классно объясняете! Но есть вопрос 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)
можно узнать, сортировка выбором в приведенном примере займет 36 переборов. (8+7+6+5+4+3+2+1). но 8 в степени 2 = 64. разница почти в 2 раза. Этим пренебрегают? или я что-то неправильно понимаю
Да все верно, константы при указании сложности в О большом игнорируются. Цель О большого показать как растет количество операций в заивисимости от роста входных данных. Интересуют прежде большие числа, при которых коэфиициенты уже не играют роли. Проще говоря мы должны сконцентрироваться именно на типе роста: линейный O(n), квадратичный O(n^2), факториальный O(n!) и т.д. Детали не особо интересуют. Так например зная, что рост у нас факториальный (O(n!)), даже если мы будем делить на 100, при больших n нам это не поможет решит задачу. В главе про жадные алгоритмы в качестве такого примера задача коммивояжёра, там при значении n=17 поиск решения требует очень много времени, на столько много, что оно к тому времени уже не нужно. Итог: мы концентрируемся на типе роста, это как с транспортными средствами, когда речь идет о перемещении из точки в А в точку Б: авто быстрее велосипеда, а самолет быстрее машины. Велосипеды тоже разные, но мы обычно не уточняем его точные характеристики, когда сравниваем с машиной. Я это так вижу.
@@ITPro-ei8cs спасибо большое. суть в том, что мы пытаемся отследить тип роста по количеству операций в зависимости от количества элементов)