|
Попробую коротко изложить суть, мы хотим в памяти отложить например 100 бит - что делает современная машина- 1+2+3+4+5+6+7 до нашего числа N. Получаем в итоге формулу N(N+1)/2 это тоже что и O(N^2) как видим мы постоянно высчитываем квадратный корень, получается для того чтобы записать ячейку размером в 100 нам потребуется работа 10000 ячеек, а 200 уже 40000, т.e. Чем длинее строка тем больше в геометрической прогрессии потребуется затрат. Только так было не всегда, на заре компьютерной эры, когда эвм были очень хилинькие ,применялся совершенно другой подход - первое условие не создавать новые ячейки, а переписывать старые, точнее не переписывать а увеличивать по довольно интересной схеме - оперируя по очереди двумя переменными- увеличивая одну в два раза и после прибавляя другую, мы экономим огромное количество памяти, приведу пример с этого сайта - мы хотим получить переменную в 9 символов - стандартным методом будет выглядеть так: = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 в сумме получаем 45 задействованных блоков памяти, а по этой методике получается так:1 + 2 + 4 + 8 + 9 сумма 24. Но чем больше данных тем больше прирост, как пишут по результатам тестов цифры такие - 88 милисекунд против всего четырех!, кому интересно на их сайте выложен микро скрипт
|