| очевидное про «о большое» |
[Jul. 15th, 2017|06:31 pm] |
отойдём от политики и социопсихологии. я тут вспомнил, что — удивительным образом — есть люди, которые считают «о-нотацию» (это которая O(1), например) «интуитивно понятной», и интуитивно понимают её неправильно. ща я напишу то, что должен знать каждый, но знают далеко не все. внемлите!
«о большое» показывает зависимость времени выполнения алгоритма от количества элементов, а не быстродействие алгоритма.
да, это совершенно разные вещи. алгоритм, у которого с каждым новым элементом время выполнения увеличивается на наносекунду, имеет сложность O(n). алгоритм, у которого с каждым новым элементом время выполнения увеличивается на миллиард лет, имеет сложность O(n). потому что константы из обычно используемой «о-нотации» убираются, как неинтересные.
ещё раз повторю: O(n) обозначает, что время исполнения алгоритма линейно зависит от количества элементов. но оно не говорит нам, какое это время. поэтому алгоритм поиска элемента в массиве, который вне зависимости от реального количества элементов всегда резервирует массив одного и того же размера (с запасом), и всегда перебирает все элементы массива (даже если нашёл элемент сразу), будет O(1). опа-опа, мы только что сделали «самый быстрый алгоритм поиска элемента в массиве, не зависящий от количества элементов» — если пишуший или читающий не понимает, как читать «о-нотацию».
если для вас вышенаписаное очевидно — здорово. но очевидно это далеко не для всех, увы. поэтому при обсуждении (или при чтении статей из интернетов) убедитесь, что собеседник (или автор статьи) правильно понимает «о большое». на всякий случай. если не лень.
на самом деле «о большое» ещё сложнее, я знаю, спасибо. но обычно его используют именно так. |
|
|
| Comments: |
| From: | (Anonymous) |
|---|
| Date: | July 15th, 2017 - 05:48 pm |
|---|
| | | (Link) |
|
не "количества элементов", а размера входных данных
![[User Picture]](http://lj.rossia.org/userpic/197531/22349) | | From: | ![[info]](http://lj.rossia.org/img/userinfo.gif) ketmar |
|---|
| Date: | July 16th, 2017 - 04:31 am |
|---|
| | | (Link) |
|
что меряют в количестве каких-либо элементов. то же самое.
| From: | (Anonymous) |
|---|
| Date: | July 15th, 2017 - 06:46 pm |
|---|
| | | (Link) |
|
thank you captain obvious!
| | From: | ketmar |
|---|
| Date: | July 16th, 2017 - 04:39 am |
|---|
| | | (Link) |
|
иногда с удивлением обнаруживаешь, что без Капитана никак. мне этот пост удобен тем, что на него можно быстро ссылку найти в logjam.
| From: | (Anonymous) |
|---|
| Date: | July 15th, 2017 - 06:47 pm |
|---|
| | | (Link) |
|
А ещё надо знать, что 95% макак, обсуждающих на форумах о-большое, все равно напишут тормозное говно.
| From: | (Anonymous) |
|---|
| Date: | July 15th, 2017 - 06:49 pm |
|---|
| | | (Link) |
|
Кстати, что думаешь о вейленде?
| From: | (Anonymous) |
|---|
| Date: | July 15th, 2017 - 07:52 pm |
|---|
| | | (Link) |
|
Пример некорректный все-таки. Когда мы говорим про о большое, мы имеем виду ассимптотику при n стремящимся к бесконечности (предполагая, что мы исследуем сферический алгоритм в вакууме, исполняющийся на какой-нибуде машине Тьюринга). Какой бы массив "с запасом" мы не взяли бы, найдется n, при котором такой алгоритм перестанет работать - а тогда и об о большом говорить бессмысленно. С точки зрения компьютер сайнс, это вообще не алгоритм, а говно.
А если исходить из того, что на практике бесконечности не встречаются, то есть такой забавный момент: поскольку в жизни n < 2^64, то log n < 64, и его можно спокойно выбрасывать из-под о большого. Алгоритмы сортировки с временем выполнения О(n) (типа radix sort) в жизни ничем не лучше алгоритмов со временем O(n log n).
| | From: | ketmar |
|---|
| Date: | July 16th, 2017 - 04:37 am |
|---|
| | | (Link) |
|
конечно, я дико всё упростил (и при этом местами сломал) в посте. но «чисто академически» O всё равно применяют только сферические академики. пост скорее для тех, кто уверен, что O(1) во всех случаях, без исключений — быстрее O(n), например. такие есть же.
про то, что для практических случаев `log n` часто можно выкинуть, я писать поостерёгся: тогда вообще разочаруются, плюнуют: «нинужно это ваше O, ничего в нём нету вообще полезного!» людей надо пугать постепенно, а не сразу, чтобы привыкли.
| From: | (Anonymous) |
|---|
| Date: | September 3rd, 2017 - 05:27 pm |
|---|
| | | (Link) |
|
Все верно, только это можно понять и объяснить гораздо проще: O(n) характеризует не быстродействие, а *масштабирование* алгоритмов. | |
