Сообщение Re[3]: Как быстрее формировать список, который после заполне от 27.01.2020 3:29
Изменено 27.01.2020 3:29 Sharowarsheg
Re[3]: Как быстрее формировать список, который после заполнения нужно отсортиров
Здравствуйте, Sharov, Вы писали:
S>Хе-хе, я все-таки угадал со вставкой О(n*logn), но я ошибался в том, что вставка в отсортированый массив будет О(logn), а она на самом деле О(n). Почему О(n) я пока не понял, из-за копирования что ли?
Да, потому что тебе нужно сдвинуть в среднем половину элементов на одну позицию для кажлой вставки.
S>Хе-хе, я все-таки угадал со вставкой О(n*logn), но я ошибался в том, что вставка в отсортированый массив будет О(logn), а она на самом деле О(n). Почему О(n) я пока не понял, из-за копирования что ли?
Да, потому что тебе нужно сдвинуть в среднем половину элементов на одну позицию для кажлой вставки.
Re[3]: Как быстрее формировать список, который после заполне
Здравствуйте, Sharov, Вы писали:
S>Хе-хе, я все-таки угадал со вставкой О(n*logn), но я ошибался в том, что вставка в отсортированый массив будет О(logn), а она на самом деле О(n). Почему О(n) я пока не понял, из-за копирования что ли?
Да, потому что тебе нужно сдвинуть в среднем половину элементов на одну позицию для каждой вставки.
S>Хе-хе, я все-таки угадал со вставкой О(n*logn), но я ошибался в том, что вставка в отсортированый массив будет О(logn), а она на самом деле О(n). Почему О(n) я пока не понял, из-за копирования что ли?
Да, потому что тебе нужно сдвинуть в среднем половину элементов на одну позицию для каждой вставки.