Здравствуйте. Вопрос по лекции. Если сложность для алгоритма, заданного разрешающим деревом это высота дерева, то почему для случая дерева сортировки сложность оценивается как O(NlogN), если высота его будет O(logN)?
Высота BST дерева в среднем O(logN), при вставке элемента в BST нужно выполнить операцию поиска - тоже O(logN), тогда при вставке N элементов будет выполнен поиск N раз, отсюда и такая сложность. Если обойдем такое дерево in order обходом, то получим отсортированный массив, но сортировка у нас тоже выполняется не за O(logN), а O(NlogN)
П*дец беда с русскими лекторами. Считают что чем сложнее предложения, чем больше умных слов, которых большинство студентов не знает, то тем круче лекция. "В порядке неубывания элементов интервальног множества", "бивалентность")) Напоминает программирование в 90-х, когда чем сложее и лаконичнее код, чем больше малоизвестных конструкций языка используется, тем круче разработчик. Ты же лекцию для студентов читаешь, а не научный доклад делаешь, пытайся объяснить все предельно просто, оставь свои сложные словечки для таких же умудренных опытом коллег.
Беда не с лекторами, а со студентами, у которых проблема со словарным запасом, а также желанием его расширять. Их даже студентами грех называть. Так...вольные слушатели)
Спасибо, отличная лекция
нормально объясняет. кто универ посещал тот поймет. Я за 2 часа до сна смотрю видео лекции.
А задачи из практики можно где-то посмотреть?.
Неплохая лекция
что с качеством лекции? выкрутил на 720 , а ощущение 2000 не покидает все полтора часа(
Подача материала, к сожалению, хромает. Лектор рассказывает сам для себя
Почему ютуб так убого растягивается на этом уроке? Расширение видео не то?
Здравствуйте. Вопрос по лекции. Если сложность для алгоритма, заданного разрешающим деревом это высота дерева, то почему для случая дерева сортировки сложность оценивается как O(NlogN), если высота его будет O(logN)?
высота будет равна log(N!)
@@TheBriks внимательно посмотрите оценку глубины, явно НЕ факториал
Высота BST дерева в среднем O(logN), при вставке элемента в BST нужно выполнить операцию поиска - тоже O(logN), тогда при вставке N элементов будет выполнен поиск N раз, отсюда и такая сложность. Если обойдем такое дерево in order обходом, то получим отсортированный массив, но сортировка у нас тоже выполняется не за O(logN), а O(NlogN)
@@kvoistinov да, N элементов * log N, полная сортировка получается - соответствует сложности сортировки линейного массива по фон Нейману
где задачи можно найти?
Чувствую себя Гомером(Симпсоном)
почему сделали такую страшную заставку
П*дец беда с русскими лекторами. Считают что чем сложнее предложения, чем больше умных слов, которых большинство студентов не знает, то тем круче лекция. "В порядке неубывания элементов интервальног множества", "бивалентность")) Напоминает программирование в 90-х, когда чем сложее и лаконичнее код, чем больше малоизвестных конструкций языка используется, тем круче разработчик. Ты же лекцию для студентов читаешь, а не научный доклад делаешь, пытайся объяснить все предельно просто, оставь свои сложные словечки для таких же умудренных опытом коллег.
Естественно понятные мат. обозначения. Чай не для веб-макак лекция, студенты не жалуются.
Гм, вы преподаватель, я угадал?
я пока еще абитуриент) поступаю только в вуз
Мне к вузу надо готовиться, факультет сложный. Лучше основы уже освоить уже сейчас)
Беда не с лекторами, а со студентами, у которых проблема со словарным запасом, а также желанием его расширять. Их даже студентами грех называть. Так...вольные слушатели)