https://discopal.ispras.ru/index.php?action=history&feed=atom&title=%D0%A1%D0%BE%D0%B7%D0%B4%D0%B0%D1%82%D1%8C_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D1%8E_%D0%B2_%D0%B4%D0%B0%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BA%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D0%B8 2026-04-14T22:32:44Z История изменений этой страницы в вики MediaWiki 1.26.4 https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D0%B7%D0%B4%D0%B0%D1%82%D1%8C_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D1%8E_%D0%B2_%D0%B4%D0%B0%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BA%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D0%B8&diff=15620&oldid=prev 2021-03-04T00:20:56Z

<p>Массовая правка: замена Временная и пространственная сложность алгоритмов/замки и ключи на Временная и пространственная сложность алгоритмов/Задачи/замки и ключи</p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 00:20, 4 марта 2021</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Строка 1:</td> <td colspan="2" class="diff-lineno">Строка 1:</td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Временная и пространственная сложность алгоритмов/замки и ключи]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Временная и пространственная сложность алгоритмов<ins class="diffchange diffchange-inline">/Задачи</ins>/замки и ключи]]</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <!-- diff cache key discopal:diff:version:1.11a:oldid:11263:newid:15620 --> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D0%B7%D0%B4%D0%B0%D1%82%D1%8C_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D1%8E_%D0%B2_%D0%B4%D0%B0%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BA%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D0%B8&diff=11263&oldid=prev 2020-05-20T20:50:05Z

<p>Массовая правка: замена :Проблемы в решении]] на :Уже не исправить]]</p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 20:50, 20 мая 2020</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l17" >Строка 17:</td> <td colspan="2" class="diff-lineno">Строка 17:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 00:34, 26 апреля 2018 (MSK): Оформите как надо. Посмотрите на название.</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 00:34, 26 апреля 2018 (MSK): Оформите как надо. Посмотрите на название.</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<del class="diffchange diffchange-inline">Проблемы в решении</del>]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<ins class="diffchange diffchange-inline">Уже не исправить</ins>]]</div></td></tr> <!-- diff cache key discopal:diff:version:1.11a:oldid:7373:newid:11263 --> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D0%B7%D0%B4%D0%B0%D1%82%D1%8C_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D1%8E_%D0%B2_%D0%B4%D0%B0%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BA%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D0%B8&diff=7373&oldid=prev 2018-04-25T21:34:23Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 21:34, 25 апреля 2018</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l17" >Строка 17:</td> <td colspan="2" class="diff-lineno">Строка 17:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 00:34, 26 апреля 2018 (MSK): Оформите как надо. Посмотрите на название.</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>[[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 00:34, 26 апреля 2018 (MSK): Оформите как надо. Посмотрите на название.</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<del class="diffchange diffchange-inline">Проблема </del>в решении]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<ins class="diffchange diffchange-inline">Проблемы </ins>в решении]]</div></td></tr> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D0%B7%D0%B4%D0%B0%D1%82%D1%8C_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D1%8E_%D0%B2_%D0%B4%D0%B0%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BA%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D0%B8&diff=7371&oldid=prev 2018-04-25T21:34:13Z

<p></p> <table class='diff diff-contentalign-left'> <col class='diff-marker' /> <col class='diff-content' /> <col class='diff-marker' /> <col class='diff-content' /> <tr style='vertical-align: top;' lang='ru'> <td colspan='2' style="background-color: white; color:black; text-align: center;">← Предыдущая</td> <td colspan='2' style="background-color: white; color:black; text-align: center;">Версия 21:34, 25 апреля 2018</td> </tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l14" >Строка 14:</td> <td colspan="2" class="diff-lineno">Строка 14:</td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>&lt;/latex&gt;</div></td></tr> <tr><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'>&#160;</td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr> <tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<del class="diffchange diffchange-inline">На проверку</del>]]</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#160;</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins class="diffchange diffchange-inline">[[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 00:34, 26 апреля 2018 (MSK): Оформите как надо. Посмотрите на название.</ins></div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>&#160;</div></td></tr> <tr><td colspan="2">&#160;</td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[Категория:<ins class="diffchange diffchange-inline">Проблема в решении</ins>]]</div></td></tr> </table>

StasFomin https://discopal.ispras.ru/index.php?title=%D0%A1%D0%BE%D0%B7%D0%B4%D0%B0%D1%82%D1%8C_%D1%81%D1%82%D0%B0%D1%82%D1%8C%D1%8E_%D0%B2_%D0%B4%D0%B0%D0%BD%D0%BD%D0%BE%D0%B9_%D0%BA%D0%B0%D1%82%D0%B5%D0%B3%D0%BE%D1%80%D0%B8%D0%B8&diff=7230&oldid=prev 2018-04-04T21:02:49Z

<p>Новая страница: «<a href="/index.php?title=%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D0%B8_%D0%BF%D1%80%D0%BE%D1%81%D1%82%D1%80%D0%B0%D0%BD%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%B7%D0%B0%D0%BC%D0%BA%D0%B8_%D0%B8_%D0%BA%D0%BB%D1%8E%D1%87%D0%B8&amp;action=edit&amp;redlink=1" class="new" title="Временная и пространственная сложность алгоритмов/замки и ключи (страница не существует)">Временная и пространственная сложность алгоритмов/замки и ключи</a> &lt;latex&gt; \\ Построим реку…»</p> <p><b>Новая страница</b></p><div>[[Временная и пространственная сложность алгоритмов/замки и ключи]]<br /> <br /> <br /> &lt;latex&gt;<br /> \\<br /> Построим рекурсивный алгоритм.\\<br /> Сначала возьмём произвольный ключ и попробуем вставить его в каждый замок. После этой процедуры у нас получится два множества замков. Меньшее и большее от этого ключа. Также мы найдём замок в который подошёл этот ключ. Сравним все оставшиеся ключи с этим замком. Это зравнение добавит в 2 множества замков по столько же ключей. То есть мы получили 2 множества в которых ключей и замков одинаковое количество.<br /> Далее продлываем те же действия только для каждого из получившихся множеств.\\<br /> На каждой итерации мы выполняем O(n) операций.<br /> Таким образом получаем рекурентное соотношение:\\<br /> T(n) = T(n-m) + T(m) + O(n). Такое же рекурентное соотношение получается и для алгоритма быстрой сортировки. Следовательно T(n) $\in$ O(nlogn) $\subset o(n^2)$.\\<br /> \\<br /> <br /> &lt;/latex&gt;<br /> <br /> [[Категория:На проверку]]</div>

Nikolay goryan