Согласно определению сложности, за N берется размер входного аргумента. Тогда временна́я и пространственная сложность — функции от именного этого N. В случае сортировки N — это размер массива (точнее, N, умноженное на размер элемента в битах). Наивный алгоритм бы взял еще столько же памяти, всё равно бы вышло O(N), что по порядку величины не отличается от умного алгоритма, который бы брал O(1) дополнительной памяти.
Почему? В самой наивной версии достаточно 2N — просто заводим вспомогательный массив того же размера. Но, насколько я понимаю, можно обойтись и кусочком фиксированного размера, тогда N+O(1).
Пример с сортировкой не совсем удачный — там размер аргумента (и результата) большой по сравнению с дополнительной памятью, которой там всего O(1). Вообще для алгоритмов окололинейной сложности эта теорема, кажется, не очень интересна.
Кстати, 1L — это они нехорошо написали. Если потом зачем-нибудь понадобится сдвигать вправо, то это будет арифметический сдвиг, а не логический, и потом тоже придется кому-то кровь-мясо-кишки собирать. Надо 1UL.
Это особенность даже не джавы, а архитектуры x86. Там инструкции сдвига работают именно так. А языки (Java, C) наследуют такое поведение и записывают себе в спецификацию.
Я как-то для удобства написал микробиблиотечку с макросами, которые позволяют делать сдвиги на произвольное количество бит, в том числе допускают отрицательный сдвиг (это значит, что меняется направление сдвига). Наверно стоит откопать этот код и выложить. Тогда их код 1L << token.charAt(i) можно было бы безопасно переписать так: shift_any(<<, 1L, token.charAt(i)).
Интересное решение. Но я бы сделал иначе: если взятие возможно (без разницы, обычное взятие или на проходе), то помечать туманом, а если невозможно — рисовать пустое поле. Смысл в том, что пешка «знает», когда поле пусто, это знание логичней изобразить без тумана.
Думал написать здесь про поднятие мужской уверенности, но передумал.
Если верить тому абзацу и картинке, где описаны нагружаемые группы мышц, то должен быть мощный стимул не столько встать на эти штуки самому, сколько поставить на них жену/подругу.
Сам посыл статьи тривиален. А вот было бы гораздо интереснее и полезнее увидеть обсуждение того, каким именно напалмом выжигать практику применения GeoIP для определения локали.
Размер программы ограничен 1536 байтами (не считая пробелы, табы и прочие служебные символы)
С такой формулировкой можно написать программу любой сложности. Можно представить себе язык, в котором кодируется всё что угодно с помощью пары символов — таба и пробела. Тогда самое трудное — упихнуть в полтора килобайта интерпретатор этого языка, но опытные участники наверно справятся.
Да, я тоже подумал, что он в принципе мог бы быть чемпионом страны, но таки поленился проверять.
На подписи к фотографии ошибка: Эдуард Ласкер (не путать с Эмануилом) не был чемпионом, хотя и был сильным шахматистом.
Да, похоже на контрпример к теореме. ;) Надо вкуривать исходник, скорее всего там есть дополнительные условия.
Согласно определению сложности, за N берется размер входного аргумента. Тогда временна́я и пространственная сложность — функции от именного этого N. В случае сортировки N — это размер массива (точнее, N, умноженное на размер элемента в битах). Наивный алгоритм бы взял еще столько же памяти, всё равно бы вышло O(N), что по порядку величины не отличается от умного алгоритма, который бы брал O(1) дополнительной памяти.
Почему? В самой наивной версии достаточно 2N — просто заводим вспомогательный массив того же размера. Но, насколько я понимаю, можно обойтись и кусочком фиксированного размера, тогда N+O(1).
Пример с сортировкой не совсем удачный — там размер аргумента (и результата) большой по сравнению с дополнительной памятью, которой там всего O(1). Вообще для алгоритмов окололинейной сложности эта теорема, кажется, не очень интересна.
В этом смысле да. Но тогда можно сказать, что вся x86 — легаси. ;)
Почему легаси? Честный сдвиг на произвольное количество разрядов стоит в аппаратуре дороже, чем этот урезанный.
Кстати,
1L— это они нехорошо написали. Если потом зачем-нибудь понадобится сдвигать вправо, то это будет арифметический сдвиг, а не логический, и потом тоже придется кому-то кровь-мясо-кишки собирать. Надо1UL.Это особенность даже не джавы, а архитектуры x86. Там инструкции сдвига работают именно так. А языки (Java, C) наследуют такое поведение и записывают себе в спецификацию.
Я как-то для удобства написал микробиблиотечку с макросами, которые позволяют делать сдвиги на произвольное количество бит, в том числе допускают отрицательный сдвиг (это значит, что меняется направление сдвига). Наверно стоит откопать этот код и выложить. Тогда их код
1L << token.charAt(i)можно было бы безопасно переписать так:shift_any(<<, 1L, token.charAt(i)).Интересное решение. Но я бы сделал иначе: если взятие возможно (без разницы, обычное взятие или на проходе), то помечать туманом, а если невозможно — рисовать пустое поле. Смысл в том, что пешка «знает», когда поле пусто, это знание логичней изобразить без тумана.
Здесь какая-то нескладушка.
Абанамат, я — ономат!
Можно считать, что такой термин уже устаканился:
> Пустоты, космические пустоты, также войды
Если верить тому абзацу и картинке, где описаны нагружаемые группы мышц, то должен быть мощный стимул не столько встать на эти штуки самому, сколько поставить на них жену/подругу.
Устоявшийся термин — уравнение теплопроводности.
Интересно, как можно было об этом догадаться, особенно в свете того, что
Это, скорее, не решение, а обход проблемы пользователем. А хорошо как-то принудить владельцев сервисов делать правильно.
Сам посыл статьи тривиален. А вот было бы гораздо интереснее и полезнее увидеть обсуждение того, каким именно напалмом выжигать практику применения GeoIP для определения локали.
С такой формулировкой можно написать программу любой сложности. Можно представить себе язык, в котором кодируется всё что угодно с помощью пары символов — таба и пробела. Тогда самое трудное — упихнуть в полтора килобайта интерпретатор этого языка, но опытные участники наверно справятся.