{"id":314538,"date":"2020-12-08T15:01:41","date_gmt":"2020-12-08T15:01:41","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=314538"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=314538","title":{"rendered":"\u0418\u0449\u0435\u043c \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u044f\u043c\u0438. User-friendly-\u0440\u0430\u0437\u0431\u043e\u0440 \u0437\u0430\u0434\u0430\u0447\u0438 \u043f\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c"},"content":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\">\u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440!<\/p>\n<p>  \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043f\u0440\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u041d\u043e\u0432\u0438\u0447\u043a\u0438 \u0447\u0430\u0441\u0442\u043e \u0432\u043e\u0441\u043f\u0440\u0438\u043d\u0438\u043c\u0430\u044e\u0442 \u0438\u0445 \u043a\u0430\u043a \u0447\u0442\u043e-\u0442\u043e \u0442\u044f\u0436\u0451\u043b\u043e\u0435, \u0441\u043b\u043e\u0436\u043d\u043e\u0435 \u0438 \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e\u0435, \u0438 \u043e\u0442\u0447\u0430\u0441\u0442\u0438 \u044d\u0442\u043e \u043f\u0440\u0430\u0432\u0434\u0430, \u043d\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u2014 \u044d\u0442\u043e \u0431\u0430\u0437\u0438\u0441. \u0410 \u0447\u0435\u043c \u043b\u0443\u0447\u0448\u0435 \u0432\u044b \u0437\u043d\u0430\u0435\u0442\u0435 \u0431\u0430\u0437\u0438\u0441 \u0441\u0432\u043e\u0435\u0439 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u0442\u0435\u043c \u0441 \u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u0440\u0435\u0443\u0441\u043f\u0435\u0435\u0442\u0435 \u0432 \u043d\u0435\u0439. <\/p>\n<p>  <a href=\"https:\/\/habr.com\/ru\/company\/yandex_praktikum\/blog\/531748\/\"><\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/3h\/jg\/ne\/3hjgneg_xjvgja3rvptjjelqyyo.jpeg\"><\/div>\n<p><\/a><\/p>\n<p>  \u0421\u0435\u0433\u043e\u0434\u043d\u044f \u043c\u044b \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u043e\u0434\u043d\u0443 \u043a\u0440\u0430\u0441\u0438\u0432\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 \u043f\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c. \u041d\u0435 \u0431\u0443\u0434\u0435\u043c \u043e\u0442\u043f\u0443\u0433\u0438\u0432\u0430\u0442\u044c \u043b\u044e\u0434\u0435\u0439 \u043e\u0442 <a href=\"https:\/\/praktikum.yandex.ru\/algorithms\/?utm_source=pr&amp;utm_medium=content&amp;utm_term=8_12_20&amp;utm_campaign=habr\">\u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c\u0438<\/a> \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0441\u0442\u0430\u0440\u0442\u0435, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432 \u043d\u0430\u0448\u0435\u043c \u0440\u0430\u0437\u0431\u043e\u0440\u0435 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043d\u0438 \u0440\u0430\u0437\u0432\u0435\u0441\u0438\u0441\u0442\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432, \u043d\u0438 \u0440\u0430\u0437\u043d\u043e\u043c\u0430\u0441\u0442\u043d\u044b\u0445 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435, \u043d\u0438 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u043d\u044b\u0445 \u0442\u0435\u0441\u0442\u043e\u0432 \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443. User-friendly algos.<\/p>\n<p>  <b>\u0412\u043e\u0442 \u0437\u0430\u0434\u0430\u0447\u0430: \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u044f\u043c\u0438.<\/b><\/p>\n<p>  \u0414\u0430\u043d \u043c\u0430\u0441\u0441\u0438\u0432 \u0438\u0437 N \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u041e\u043d \u043d\u0438\u043a\u0430\u043a \u043d\u0435 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d, \u0430 \u0447\u0438\u0441\u043b\u0430 \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0442\u044c\u0441\u044f. \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u043c\u044b \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043b\u0438 \u0435\u0433\u043e \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u043b\u0438 \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u043c\u0435\u0436\u0434\u0443 \u043a\u0430\u0436\u0434\u043e\u0439 \u043f\u0430\u0440\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0442\u0430\u043a\u0443\u044e \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u0438 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c.<\/p>\n<p>  \u0421\u043b\u043e\u0436\u043d\u043e? \u041c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e \u0434\u043e \u0442\u043e\u0433\u043e, \u043a\u0430\u043a \u043d\u0430\u0436\u043c\u0451\u0442\u0435 \u00ab\u0427\u0438\u0442\u0430\u0442\u044c \u0434\u0430\u043b\u044c\u0448\u0435\u00bb, \u0430 \u043f\u043e\u0442\u043e\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435.<br \/>  <a name=\"habracut\"><\/a><br \/>  \u0418\u0442\u0430\u043a, \u043f\u043e\u0435\u0445\u0430\u043b\u0438. \u041c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u044f\u043c\u0438.<\/p>\n<p>  \u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u0438\u043c\u0435\u0440:<br \/>  \u041f\u0443\u0441\u0442\u044c \u0434\u0430\u043d \u043c\u0430\u0441\u0441\u0438\u0432 \u0438\u0437 N=11 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432.<br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/929\/fec\/f51\/929fecf510dfd94bb653601953983ab4.svg\" alt=\"$A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15]$\" data-tex=\"inline\"><\/math><\/p>\n<p>  C\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0435\u0448\u0438\u043c \u0437\u0430\u0434\u0430\u0447\u0443 \u043d\u0430\u0438\u0432\u043d\u043e, \u044d\u0442\u043e \u0447\u0430\u0441\u0442\u043e \u043f\u043e\u043c\u043e\u0433\u0430\u0435\u0442. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0438\u043c\u0435\u043d\u043d\u043e \u0442\u043e, \u0447\u0442\u043e \u043e\u0442 \u043d\u0430\u0441 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0443\u0441\u043b\u043e\u0432\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u2014 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0447\u0438\u0441\u043b\u0430 \u0438 \u043d\u0430\u0439\u0442\u0438 \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c\u0438. \u0412 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u0442\u043e\u0433\u043e, \u043a\u0430\u043a\u0443\u044e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c, \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0431\u0443\u0434\u0435\u0442 \u0432\u0430\u0440\u044c\u0438\u0440\u043e\u0432\u0430\u0442\u044c\u0441\u044f. <\/p>\n<p>  \u0415\u0441\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c <i>qsort <\/i>\u0438\u043b\u0438 <i>mergesort<\/i>, \u0442\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d81\/55e\/b26\/d8155eb26fbb060d2c4773c5fe611b9b.svg\" alt=\"$O(N log N)$\" data-tex=\"inline\"><\/math>. \u0415\u0441\u043b\u0438 \u043d\u0430\u043c \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e, \u0447\u0442\u043e \u0447\u0438\u0441\u043b\u0430 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u044b \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u043b\u043e\u0442\u043d\u043e \u043d\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435 \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b, \u0442\u043e \u043c\u043e\u0436\u043d\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0443 \u043f\u043e\u0434\u0441\u0447\u0451\u0442\u043e\u043c. \u0422\u043e\u0433\u0434\u0430 \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/41f\/e72\/fd4\/41fe72fd46b9ef5d0e211d16d9bf23cc.svg\" alt=\"$O(U + N)$\" data-tex=\"inline\"><\/math>, \u0433\u0434\u0435 U \u2014 \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c. \u0421\u043b\u0443\u0447\u0430\u0439 \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0435\u0434\u043a\u0438\u0439, \u043d\u043e \u0441\u0442\u043e\u0438\u0442 \u043f\u043e\u043c\u043d\u0438\u0442\u044c \u043f\u0440\u043e \u0442\u0430\u043a\u0443\u044e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c.<\/p>\n<p>  \u041f\u043e\u0441\u043b\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u043c\u0430\u0441\u0441\u0438\u0432:<br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d0f\/660\/5e4\/d0f6605e4e264b0be4abd374afec34bb.svg\" alt=\"$As = [-3, -2, -1, 3, 4, 10, 10, 15, 20, 21, 22]$\" data-tex=\"inline\"><\/math><br \/>  \u0412\u044b\u043f\u0438\u0448\u0435\u043c \u043c\u0430\u0441\u0441\u0438\u0432 \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u0435\u0439:<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/391\/07c\/1ff\/39107c1ff7f470f424022d96cbdbf9d2.svg\" alt=\"$D = [1, 1, 4, 1, 6, 0, 5, 5, 1, 1]$\" data-tex=\"inline\"><\/math><br \/>  \u041f\u043e\u043b\u0443\u0447\u0430\u0435\u043c, \u0447\u0442\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 6.<\/p>\n<p>  \u0422\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u0434\u0443\u043c\u0430\u0435\u043c, \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0440\u0435\u0448\u0438\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u0431\u044b\u0441\u0442\u0440\u0435\u0435? \u041f\u0440\u0438 \u043f\u0435\u0440\u0435\u0431\u043e\u0440\u0435 \u043f\u0430\u0440 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c \u043c\u043d\u043e\u0433\u043e \u043f\u0430\u0440 \u0441 \u043c\u0430\u043b\u0435\u043d\u044c\u043a\u043e\u0439 \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c\u044e. \u0422\u0430\u043a\u0438\u0435 \u043f\u0430\u0440\u044b, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u0438 \u043d\u0435 \u0441\u043c\u043e\u0433\u0443\u0442 \u043d\u0438\u043a\u043e\u0433\u0434\u0430 \u0434\u0430\u0442\u044c \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c. \u0418 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/0b3\/c81\/de2\/0b3c81de26a34919f96fc1b8a06e516e.svg\" alt=\"$N-1$\" data-tex=\"inline\"><\/math> \u043f\u0430\u0440\u0430 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u0447\u0438\u0441\u0435\u043b, \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u043e\u043c \u0438 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u043e\u043c \u043f\u0443\u0441\u0442\u044c \u0440\u0430\u0432\u043d\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d07\/cc5\/b26\/d07cc5b26db621faab45e0e0b54ede62.svg\" alt=\"$U$\" data-tex=\"inline\"><\/math>. \u0422\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u0438 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0434\u043e\u043b\u0436\u043d\u043e \u0431\u044b\u0442\u044c \u0445\u043e\u0442\u044f \u0431\u044b <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/eca\/bff\/228\/ecabff228cda4922172346e6c4b7fe0e.svg\" alt=\"$U \/ (N - 1)$\" data-tex=\"inline\"><\/math>. \u042d\u0442\u0430 \u043e\u0446\u0435\u043d\u043a\u0430 \u0432\u0435\u0440\u043d\u0430 \u043f\u043e \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0443 \u0414\u0438\u0440\u0438\u0445\u043b\u0435. <\/p>\n<blockquote><p>\u0415\u0441\u043b\u0438 \u0433\u043e\u043b\u0443\u0431\u0438 \u0440\u0430\u0441\u0441\u0430\u0436\u0435\u043d\u044b \u0432 \u043a\u043b\u0435\u0442\u043a\u0438, \u043f\u0440\u0438\u0447\u0451\u043c \u0447\u0438\u0441\u043b\u043e \u0433\u043e\u043b\u0443\u0431\u0435\u0439 \u0431\u043e\u043b\u044c\u0448\u0435 \u0447\u0438\u0441\u043b\u0430 \u043a\u043b\u0435\u0442\u043e\u043a, \u0442\u043e \u0445\u043e\u0442\u044f \u0431\u044b \u0432 \u043e\u0434\u043d\u043e\u0439 \u0438\u0437 \u043a\u043b\u0435\u0442\u043e\u043a \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0431\u043e\u043b\u0435\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0433\u043e\u043b\u0443\u0431\u044f.<\/p><\/blockquote>\n<p>  <\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/1e\/px\/9f\/1epx9f1ew_rpkyahnczjhk5eu_q.jpeg\"><\/div>\n<p>  <i>9 \u043a\u043b\u0435\u0442\u043e\u043a \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 10 \u0433\u043e\u043b\u0443\u0431\u0435\u0439, \u043f\u043e \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0443 \u0414\u0438\u0440\u0438\u0445\u043b\u0435, \u0445\u043e\u0442\u044f \u0431\u044b \u0432 \u043e\u0434\u043d\u043e\u0439 \u043a\u043b\u0435\u0442\u043a\u0435 \u043d\u0430\u0445\u043e\u0434\u044f\u0442\u0441\u044f \u0431\u043e\u043b\u0435\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0433\u043e\u043b\u0443\u0431\u044f (<a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9F%D1%80%D0%B8%D0%BD%D1%86%D0%B8%D0%BF_%D0%94%D0%B8%D1%80%D0%B8%D1%85%D0%BB%D0%B5_(%D0%BA%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%B8%D0%BA%D0%B0)\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a>)<\/i><\/p>\n<p>  \u041f\u0443\u0441\u0442\u044c <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d59\/dbe\/08f\/d59dbe08f60261f23b53472f9fba8d78.svg\" alt=\"$D[1] = As[2]-As[1]$\" data-tex=\"inline\"><\/math>, \u2026 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b37\/e2a\/5ad\/b37e2a5ad075ed6b3fb673b2e6d9c82c.svg\" alt=\"$D[n - 1] = As[n] - As[n - 1]$\" data-tex=\"inline\"><\/math>,<math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d04\/b82\/cfe\/d04b82cfe72bf71abbd5ea8567192c69.svg\" alt=\"$ As[i]$\" data-tex=\"inline\"><\/math> \u2014 i-\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u0422\u043e\u0433\u0434\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/a80\/436\/46a\/a8043646a6360adf3273d6a036c247ea.svg\" alt=\"$D[i] &gt;= 0, D[1] + \u2026 + D[N-1] = U$\" data-tex=\"inline\"><\/math>. <\/p>\n<p>  \u0415\u0441\u043b\u0438 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u0442\u044c, \u0447\u0442\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0438\u0437 \u0432\u0441\u0435\u0445 D[i] \u043c\u0435\u043d\u044c\u0448\u0435 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/eca\/bff\/228\/ecabff228cda4922172346e6c4b7fe0e.svg\" alt=\"$U\/(N-1)$\" data-tex=\"inline\"><\/math>, \u0442\u043e \u0432\u0441\u044f \u0441\u0443\u043c\u043c\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f1b\/08d\/e3a\/f1b08de3a2ccb2642a441e3d0120a0da.svg\" alt=\"$D[1] + \u2026 + D[N-1] $\" data-tex=\"inline\"><\/math> \u0431\u0443\u0434\u0435\u0442 \u0441\u0442\u0440\u043e\u0433\u043e \u043c\u0435\u043d\u044c\u0448\u0435 U \u2014 \u043f\u0440\u043e\u0442\u0438\u0432\u043e\u0440\u0435\u0447\u0438\u0435.<\/p>\n<p>  \u041e\u0442\u043b\u0438\u0447\u043d\u043e, \u043c\u044b \u043f\u043e\u043b\u0443\u0447\u0438\u043b\u0438 \u043d\u0438\u0436\u043d\u044e\u044e \u043e\u0446\u0435\u043d\u043a\u0443 \u043d\u0430 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c! \u0422\u0435\u043f\u0435\u0440\u044c \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u043a\u0430\u043a-\u0442\u043e \u043b\u043e\u043a\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u0442\u044c \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u0431\u043b\u0438\u0437\u043a\u0438\u0435 \u0434\u0440\u0443\u0433 \u043a \u0434\u0440\u0443\u0433\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u2014 \u0440\u0430\u0437\u043e\u0431\u044c\u0451\u043c \u043e\u0442\u0440\u0435\u0437\u043e\u043a \u043e\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0434\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u0430 \u043f\u043e\u043b\u0443\u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b\u044b \u0434\u043b\u0438\u043d\u043e\u0439 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/1e6\/f98\/157\/1e6f9815708b56615c45e328086c6537.svg\" alt=\"$L=U\/(N-1)$\" data-tex=\"inline\"><\/math>. \u041a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u043e\u043f\u0430\u0434\u0451\u0442 \u0440\u043e\u0432\u043d\u043e \u0432 \u043e\u0434\u0438\u043d \u043f\u043e\u043b\u0443\u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b. \u041f\u043e\u043b\u0443\u0447\u0438\u043c \u0440\u0430\u0437\u0431\u0438\u0435\u043d\u0438\u0435 \u0432\u0441\u0435\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u043d\u0430 \u043d\u0435\u043f\u0435\u0440\u0435\u0441\u0435\u043a\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u0433\u0440\u0443\u043f\u043f\u044b, \u0438\u0445 \u0435\u0449\u0451 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 \u0431\u0430\u0442\u0447\u0430\u043c\u0438. <\/p>\n<p>  \u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u0432 \u043a\u0430\u043a\u043e\u0439 \u0438\u043c\u0435\u043d\u043d\u043e \u0438\u0437 \u043d\u0438\u0445 \u043f\u043e\u043f\u0430\u043b \u044d\u043b\u0435\u043c\u0435\u043d\u0442 x, \u043e\u0447\u0435\u043d\u044c \u043f\u0440\u043e\u0441\u0442\u043e \u2014 \u043d\u0430\u0434\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c (\u043d\u0443\u043c\u0435\u0440\u0443\u0435\u043c \u0441 \u0435\u0434\u0438\u043d\u0438\u0446\u044b), \u0433\u0434\u0435 a_min \u2014 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 A, \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0437\u0430 \u043e\u0434\u0438\u043d \u043f\u0440\u043e\u0445\u043e\u0434 \u043f\u043e \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c\u0443 \u043c\u0430\u0441\u0441\u0438\u0432\u0443. \u0418\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u2014 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0441 \u0442\u0430\u043a\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u043b\u0443\u0447\u0448\u0435 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u043c \u0431\u0430\u0442\u0447\u043e\u043c. <\/p>\n<p>  \u041d\u0430 \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043e \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u0438\u0437 \u043e\u043f\u0438\u0441\u0430\u043d\u043d\u043e\u0433\u043e \u0432\u044b\u0448\u0435 \u043f\u0440\u0438\u043c\u0435\u0440\u0430. \u0414\u043b\u044f \u044f\u0441\u043d\u043e\u0441\u0442\u0438 \u043f\u0440\u043e\u0434\u0435\u043b\u0430\u0435\u043c \u044d\u0442\u0443 \u043f\u0440\u043e\u0446\u0435\u0434\u0443\u0440\u0443 \u0440\u0443\u043a\u0430\u043c\u0438:<\/p>\n<p>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/673\/488\/ebe\/673488ebea8d96494ee8eded873f327e.svg\" alt=\"$U = 22 - (-3) = 25, N = 11 =&gt; L = 25\/(11-1) = 2.5$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/929\/fec\/f51\/929fecf510dfd94bb653601953983ab4.svg\" alt=\"$A = [-1, -3, 10, 20, 21, 4, 3, 22, 10, -2, 15]$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b8f\/6ec\/4ac\/b8f6ec4ac770cb67a73c9bd975060875.svg\" alt=\"$(-1 - (-3)) \/ 2.5 = 0.8 =&gt; batch = 1$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/c8f\/28d\/c96\/c8f28dc9631594cbb7c05380d0dd9da7.svg\" alt=\"$(-3 - (-3)) \/ 2.5 = 0 =&gt; batch = 1$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/d56\/06f\/a12\/d5606fa12c0fd44979765bfa5e8a9b4d.svg\" alt=\"$(10 - (-3)) \/ 2.5 = 13\/2.5 = 5.2 =&gt;batch = 6$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/eca\/115\/9b5\/eca1159b58c0653b02856ea2ca9809a1.svg\" alt=\"$(20 - (-3)) \/ 2.5 = 23\/2.5 = 9.2 =&gt; batch = 10$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/9a7\/b4e\/3ff\/9a7b4e3ffa6a8091cc86a3949e9921a2.svg\" alt=\"$(21 - (-3)) \/ 2.5 = 24\/2.5 = 9.6 =&gt; batch = 10$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/082\/ee7\/0ee\/082ee70ee271404080bcc2b08f46dfd9.svg\" alt=\"$(4 - (-3)) \/ 2.5 = 7\/2.5 = 2.8 =&gt; batch = 3$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/003\/a32\/f79\/003a32f79405a864e4d771684a8f93c7.svg\" alt=\"$(3 - (-3)) \/ 2.5 = 6\/2.5 = 2.4 =&gt; batch = 3$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/965\/d08\/eeb\/965d08eebfb09dcba58280a70292f1e0.svg\" alt=\"$(22 - (-3)) \/ 2.5 = 10 =&gt; batch = 11$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bbb\/ff1\/bc7\/bbbff1bc75df3e106947bf870388c333.svg\" alt=\"$(10 - (-3)) \/ 2.5 = 5.2 =&gt; batch = 6$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/b8e\/6e3\/150\/b8e6e3150ea86c14f927db58810d6d62.svg\" alt=\"$(-2 - (-3)) \/ 2.5 = 0.4 =&gt; batch = 1$\" data-tex=\"inline\"><\/math><br \/>  <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/4fa\/648\/81b\/4fa64881b478b83cbc44249fe5d6157c.svg\" alt=\"$(15 - (-3)) \/ 2.5 = 7.2 =&gt; batch = 8$\" data-tex=\"inline\"><\/math><\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/i_\/nf\/am\/i_nfamn0qrr4zz3fip3u-ravzea.png\"><\/div>\n<p>  \u0420\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435 \u043f\u043e \u0431\u0430\u0442\u0447\u0430\u043c \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0438 \u0442\u0440\u0435\u0431\u0443\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3b3\/7f3\/0f2\/3b37f30f255db9e1e93d63099fa0d62c.svg\" alt=\"$O(n)$\" data-tex=\"inline\"><\/math> \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u0430\u043c\u044f\u0442\u0438. \u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u0431\u0430\u0442\u0447\u0430 \u043d\u0435 \u043c\u043e\u0433\u0443\u0442 \u0434\u0430\u0442\u044c \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430\u043c\u0438. \u041c\u044b \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e \u043f\u043e\u0434\u043e\u0431\u0440\u0430\u043b\u0438 \u0435\u0433\u043e \u0440\u0430\u0437\u043c\u0435\u0440 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c.<\/p>\n<p>  \u0413\u0434\u0435 \u043c\u043e\u0433\u0443\u0442 \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c\u0441\u044f \u0434\u0432\u0430 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u043f\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430? \u041a\u043e\u043d\u0435\u0447\u043d\u043e \u0436\u0435, \u0432 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u043d\u0435\u043f\u0443\u0441\u0442\u044b\u0445 \u0431\u0430\u0442\u0447\u0430\u0445! \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043d\u0430 \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0438\u0437 \u0442\u0440\u0435\u0442\u044c\u0435\u0433\u043e \u0438 \u0448\u0435\u0441\u0442\u043e\u0433\u043e \u0431\u0430\u0442\u0447\u0430 \u043c\u043e\u0433\u0443\u0442 \u0438\u0434\u0442\u0438 \u043f\u043e\u0434\u0440\u044f\u0434 \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435, \u0442\u0430\u043a \u043a\u0430\u043a \u0431\u0430\u0442\u0447\u0438 \u043c\u0435\u0436\u0434\u0443 \u043d\u0438\u043c\u0438 \u043f\u0443\u0441\u0442\u044b\u0435. \u041f\u043e\u043d\u044f\u0442\u043d\u043e, \u0447\u0442\u043e \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u043c\u0438 \u0431\u0443\u0434\u0443\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u2014 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c \u0438\u0437 3-\u0433\u043e \u0431\u0430\u0442\u0447\u0430 \u0438 \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u0438\u0437 6-\u0433\u043e. \u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e, \u043a\u0430\u043d\u0434\u0438\u0434\u0430\u0442\u0430\u043c\u0438 \u043d\u0430 \u043f\u0430\u0440\u0443 \u0441 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c\u044e \u0431\u0443\u0434\u0443\u0442 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0431\u0430\u0442\u0447\u0430 \u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0442\u0440\u0435\u0442\u044c\u0435\u0433\u043e.<\/p>\n<p>  \u0412\u044b\u043f\u0438\u0448\u0435\u043c \u0432\u0441\u0435 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0435 \u043f\u0430\u0440\u044b \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u0434\u0430\u0442\u044c \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c. \u041e\u0431\u043e\u0437\u043d\u0430\u0447\u0438\u043c \u043a\u0430\u043a min(i) \u2014 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0432 i-\u0439 \u0433\u0440\u0443\u043f\u043f\u0435, \u043a\u0430\u043a max(i) \u2014 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442.<\/p>\n<p>  max(1) = -1 min(3) = 3<br \/>  max(3) = 4 min(6) = 10<br \/>  max(6) = 10 min(8) = 15<br \/>  max(8) = 15 min(10) = 20<br \/>  max(10) = 21 min(11) = 22<\/p>\n<p>  \u041c\u044b \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u043b\u0438 \u043f\u0430\u0440\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0441\u0442\u043e\u0438\u0442 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0442\u044c. \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043e\u0434\u0438\u043d \u043f\u0440\u043e\u0445\u043e\u0434 \u043f\u043e \u0432\u0441\u0435\u043c \u0431\u0430\u0442\u0447\u0430\u043c, \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0442\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u043d\u0435\u043f\u0443\u0441\u0442\u043e\u0439 \u0431\u0430\u0442\u0447 \u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u043d\u0451\u043c. \u041a\u043e\u0433\u0434\u0430 \u043c\u044b \u043d\u0430\u0442\u043a\u043d\u0451\u043c\u0441\u044f \u043d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u043d\u0435\u043f\u0443\u0441\u0442\u043e\u0439 \u0431\u0430\u0442\u0447, \u0442\u043e \u043d\u0430\u0439\u0434\u0451\u043c \u0432 \u043d\u0451\u043c \u043c\u0438\u043d\u0438\u043c\u0443\u043c \u0438 \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u043e\u0431\u043d\u043e\u0432\u0438\u0442\u044c \u043e\u0442\u0432\u0435\u0442.<\/p>\n<p>  \u041f\u043e\u0440\u0430\u0434\u0443\u0435\u043c\u0441\u044f \u2014 \u043c\u044b \u0440\u0435\u0448\u0438\u043b\u0438 \u0437\u0430\u0434\u0430\u0447\u0443 \u0437\u0430 \u0432\u0440\u0435\u043c\u044f <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/11b\/bac\/909\/11bbac909816a3563f0b61feec7a26f4.svg\" alt=\"$O(N)$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  \u041d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435, \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043b\u0438 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u0443\u044e \u0438\u0434\u0435\u044e \u0438 \u043f\u043e \u0441\u0443\u0442\u0438 \u043f\u0440\u043e\u0434\u0435\u043b\u0430\u043b\u0438 \u043f\u0435\u0440\u0432\u044b\u0435 \u0448\u0430\u0433\u0438 \u043a\u0430\u0440\u043c\u0430\u043d\u043d\u043e\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0438, \u0432 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u0435 \u0435\u0451 \u043d\u0430\u0437\u044b\u0432\u0430\u044e\u0442 <a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%91%D0%BB%D0%BE%D1%87%D0%BD%D0%B0%D1%8F_%D1%81%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0\">bucket-sort<\/a>. <\/p>\n<p>  <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/iv\/mz\/ma\/ivmzmaxlmwg1ffvswwq3b_6jcce.png\"><br \/>  <i>\u042d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0440\u0430\u0441\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u044e\u0442\u0441\u044f \u043f\u043e \u043a\u043e\u0440\u0437\u0438\u043d\u0430\u043c, \u0430 \u043f\u043e\u0442\u043e\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b \u0432 \u043a\u0430\u0436\u0434\u043e\u0439 \u043a\u043e\u0440\u0437\u0438\u043d\u0435 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u044e\u0442\u0441\u044f<br \/>  <\/i><\/p>\n<p>  \u0412 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043e\u043d\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0437\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/bfc\/4d5\/67c\/bfc4d567c7180cccd2d41ac8602d45ef.svg\" alt=\"$O(n^2)$\" data-tex=\"inline\"><\/math>, \u043d\u043e \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u043f\u0440\u0438 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u0431\u0430\u0442\u0447\u0435\u0439 \u0438 \u0440\u0430\u0432\u043d\u043e\u043c\u0435\u0440\u043d\u043e\u043c \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/3b3\/7f3\/0f2\/3b37f30f255db9e1e93d63099fa0d62c.svg\" alt=\"$O(n)$\" data-tex=\"inline\"><\/math>.<\/p>\n<p>  \u00ab\u041d\u043e \u043f\u043e\u0441\u0442\u043e\u0439\u0442\u0435, \u0430 \u043a\u0430\u043a \u0436\u0435 \u0441\u043b\u0443\u0447\u0430\u0439, \u043a\u043e\u0433\u0434\u0430 <math><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/formulas\/f36\/443\/716\/f36443716dfa1ed24667cd94328751c3.svg\" alt=\"$U=0$\" data-tex=\"inline\"><\/math>, \u043f\u043e\u0447\u0435\u043c\u0443 \u0432\u044b \u043d\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043b\u0438 \u0435\u0433\u043e?\u00bb, \u2014 \u0441\u043f\u0440\u043e\u0441\u0438\u0442 \u0432\u043d\u0438\u043c\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0447\u0438\u0442\u0430\u0442\u0435\u043b\u044c. \u042d\u0442\u043e\u0442 \u0441\u043b\u0443\u0447\u0430\u0439 \u0432\u044b\u0440\u043e\u0436\u0434\u0435\u043d\u043d\u044b\u0439, \u0432\u043e\u0442 \u043c\u044b \u0435\u0433\u043e \u0438 \u043d\u0435 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0435\u043b\u0438, \u043d\u043e \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u044d\u0442\u043e \u0441\u0435\u0439\u0447\u0430\u0441 \u0434\u043b\u044f \u043f\u043e\u043b\u043d\u043e\u0442\u044b \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432. <\/p>\n<p>  \u0415\u0441\u043b\u0438 \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u043c\u0435\u0436\u0434\u0443 \u043c\u0438\u043d\u0438\u043c\u0443\u043c\u043e\u043c \u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0443\u043c\u043e\u043c \u0440\u0430\u0432\u043d\u043e \u043d\u0443\u043b\u044e, \u0442\u043e \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0430\u044f \u0440\u0430\u0437\u043d\u0438\u0446\u0430 \u0442\u043e\u0436\u0435 \u0440\u0430\u0432\u043d\u0430 \u043d\u0443\u043b\u044e. \u0421\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e, \u044d\u0442\u043e \u0432\u0441\u0451.<\/p><\/div>\n<p> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/company\/yandex_praktikum\/blog\/531748\/\"> https:\/\/habr.com\/ru\/company\/yandex_praktikum\/blog\/531748\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"\n<div class=\"post__text post__text-html post__text_v1\" id=\"post-content-body\">\u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440!<\/p>\n<p>  \u0414\u0430\u0432\u0430\u0439\u0442\u0435 \u043f\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043f\u0440\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u041d\u043e\u0432\u0438\u0447\u043a\u0438 \u0447\u0430\u0441\u0442\u043e \u0432\u043e\u0441\u043f\u0440\u0438\u043d\u0438\u043c\u0430\u044e\u0442 \u0438\u0445 \u043a\u0430\u043a \u0447\u0442\u043e-\u0442\u043e \u0442\u044f\u0436\u0451\u043b\u043e\u0435, \u0441\u043b\u043e\u0436\u043d\u043e\u0435 \u0438 \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e\u0435, \u0438 \u043e\u0442\u0447\u0430\u0441\u0442\u0438 \u044d\u0442\u043e \u043f\u0440\u0430\u0432\u0434\u0430, \u043d\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u2014 \u044d\u0442\u043e \u0431\u0430\u0437\u0438\u0441. \u0410 \u0447\u0435\u043c \u043b\u0443\u0447\u0448\u0435 \u0432\u044b \u0437\u043d\u0430\u0435\u0442\u0435 \u0431\u0430\u0437\u0438\u0441 \u0441\u0432\u043e\u0435\u0439 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u0442\u0435\u043c \u0441 \u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u044c\u044e \u043f\u0440\u0435\u0443\u0441\u043f\u0435\u0435\u0442\u0435 \u0432 \u043d\u0435\u0439. <\/p>\n<p>  <a href=\"https:\/\/habr.com\/ru\/company\/yandex_praktikum\/blog\/531748\/\"><\/p>\n<div style=\"text-align:center;\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/3h\/jg\/ne\/3hjgneg_xjvgja3rvptjjelqyyo.jpeg\"><\/div>\n<p><\/a><\/p>\n<p>  \u0421\u0435\u0433\u043e\u0434\u043d\u044f \u043c\u044b \u043f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u043e\u0434\u043d\u0443 \u043a\u0440\u0430\u0441\u0438\u0432\u0443\u044e \u0437\u0430\u0434\u0430\u0447\u0443 \u043f\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c. \u041d\u0435 \u0431\u0443\u0434\u0435\u043c \u043e\u0442\u043f\u0443\u0433\u0438\u0432\u0430\u0442\u044c \u043b\u044e\u0434\u0435\u0439 \u043e\u0442 <a href=\"https:\/\/praktikum.yandex.ru\/algorithms\/?utm_source=pr&amp;utm_medium=content&amp;utm_term=8_12_20&amp;utm_campaign=habr\">\u0440\u0430\u0431\u043e\u0442\u044b \u0441 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c\u0438<\/a> \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0441\u0442\u0430\u0440\u0442\u0435, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0432 \u043d\u0430\u0448\u0435\u043c \u0440\u0430\u0437\u0431\u043e\u0440\u0435 \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043d\u0438 \u0440\u0430\u0437\u0432\u0435\u0441\u0438\u0441\u0442\u044b\u0445 \u0434\u0435\u0440\u0435\u0432\u044c\u0435\u0432 \u043e\u0442\u0440\u0435\u0437\u043a\u043e\u0432, \u043d\u0438 \u0440\u0430\u0437\u043d\u043e\u043c\u0430\u0441\u0442\u043d\u044b\u0445 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043e \u0440\u044e\u043a\u0437\u0430\u043a\u0435, \u043d\u0438 \u0432\u0435\u0440\u043e\u044f\u0442\u043d\u043e\u0441\u0442\u043d\u044b\u0445 \u0442\u0435\u0441\u0442\u043e\u0432 \u043d\u0430 \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u0443. User-friendly algos.<\/p>\n<p>  <b>\u0412\u043e\u0442 \u0437\u0430\u0434\u0430\u0447\u0430: \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u043c\u0435\u0436\u0434\u0443 \u0441\u043e\u0441\u0435\u0434\u044f\u043c\u0438.<\/b><\/p>\n<p>  \u0414\u0430\u043d \u043c\u0430\u0441\u0441\u0438\u0432 \u0438\u0437 N \u0446\u0435\u043b\u044b\u0445 \u0447\u0438\u0441\u0435\u043b. \u041e\u043d \u043d\u0438\u043a\u0430\u043a \u043d\u0435 \u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0435\u043d, \u0430 \u0447\u0438\u0441\u043b\u0430 \u043c\u043e\u0433\u0443\u0442 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0442\u044c\u0441\u044f. \u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0447\u0442\u043e \u043c\u044b \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043b\u0438 \u0435\u0433\u043e \u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u043b\u0438 \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u043c\u0435\u0436\u0434\u0443 \u043a\u0430\u0436\u0434\u043e\u0439 \u043f\u0430\u0440\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u041d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043d\u0430\u0439\u0442\u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0442\u0430\u043a\u0443\u044e \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u0438 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e \u043d\u0430\u0438\u0431\u043e\u043b\u0435\u0435 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u0441\u043f\u043e\u0441\u043e\u0431\u043e\u043c.<\/p>\n<p>  \u0421\u043b\u043e\u0436\u043d\u043e? \u041c\u043e\u0436\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u044d\u0442\u043e \u0434\u043e \u0442\u043e\u0433\u043e, \u043a\u0430\u043a \u043d\u0430\u0436\u043c\u0451\u0442\u0435 \u00ab\u0427\u0438\u0442\u0430\u0442\u044c \u0434\u0430\u043b\u044c\u0448\u0435\u00bb, \u0430 \u043f\u043e\u0442\u043e\u043c \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u043c \u0440\u0435\u0448\u0435\u043d\u0438\u0435.  <\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-314538","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/314538","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=314538"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/314538\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=314538"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=314538"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=314538"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}