Руководство по javascript, часть 5: массивы и циклы

Анализ сложности алгоритмов

• С увеличения размера входных данных обычно растет и сложность алгоритма, а следовательно, и время его выполнения. Сложность алгоритма принято называть порядком роста, который чаще всего представляется в виде нотации O-большое (от немецкого — порядок).


• Нотация О — большое – это всего лишь математический признак, который дает представление о ресурсах, потребляемых алгоритмом. Практически результаты могут быть разными. Но, как правило, это хорошая практика – пытаться снизить сложность алгоритмов.

1.1 Константный — O(1)

• Порядок роста O(1) означает, что вычислительная сложность алгоритма не зависит от размера входных данных. Следует помнить, однако, что единица в формуле не значит, что алгоритм выполняется за одну операцию или требует очень мало времени

Важно то, что это время не зависит от входных данных

1.2 Линейный — O(n)

• Порядок роста O(n) означает, что сложность алгоритма линейно растет с увеличением входного массива данных. Если алгоритм обрабатывает один элемент пять миллисекунд, то можно ожидать, что тысяча элементов обрабатываются за пять секунд. Такие алгоритмы легко узнать по наличию цикла по каждому элементу входного массива.

• Фрагмент алгоритма вычисления сложности О(n) на алгоритмическом языке С++

1.3 Логарифмический – O( log n)

• Порядок роста O( log n) означает, что время выполнения алгоритма растет логарифмически с увеличением размера входного массива данных, при этом в анализе алгоритмов по умолчанию используется логарифм по основанию 2. Большинство алгоритмов, работающих по принципу «деления пополам», имеют логарифмическую сложность. Например, метод Contains — бинарного дерева поиска (binary search tree) также имеет порядок роста O(log n).

1.4 Линеарифметический — O(n · log n))

• Линеарифметический (или линейно-логарифмический) алгоритм имеет порядок роста O(n ∙ log n). Некоторые алгоритмы, типа «разделяй и властвуй», например, сортировка слиянием и быстрая сортировка, попадают в эту категорию.

1.5 Квадратичный — O(n2)

• Время работы алгоритма с порядком роста O(n2) зависит от квадрата размера входного массива. Несмотря на то, что такой ситуации иногда не избежать, квадратичная сложность — повод пересмотреть используемые алгоритмы или структуры данных.

• Например, если массив из тысячи элементов потребует 1 000 000 операций, массив из миллиона элементов потребует 1 000 000 000 000 операций. Если одна операция требует миллисекунду для выполнения, то квадратичный алгоритм будет обрабатывать миллион элементов 32 года.

• Таким образом, при измерении сложности алгоритмов учитываются: количество операций, требуемых для завершения работы — вычислительная сложность, и объем ресурсов, в частности, памяти, который необходим алгоритму — пространственная сложность.

• Алгоритм, который выполняется в десять раз быстрее, но использует в десять раз больше памяти, может вполне подходить для серверной машины с большим объемом памяти. Но на встроенных системах, где количество памяти ограничено, такой алгоритм использовать нельзя .

Сравнительный анализ времени работы алгоритмов

• Алгоритмы сортировки, описанные в текущей главе, используют разные методы и обладают различными характеристиками. Сведены в таблицу:

Сортировка Время работы Метод Область использования
Вставкой O(n2) Вставка Очень малые массивы
Выбором O(n2) Выбор Очень малые массивы
Пузырьковая O(n2) Двусторонние прохождения, ограничения рассматриваемых пределов Очень малые и частично сортированные массивы
Пирамидальная O(n·log n) Кучи, хранение полных деревьев в массиве Крупные массивы с неизвестным распределением
Быстрая O(n·log n)O(n2)-худший «Разделяй и властвуй», перемещение элементов в позицию, рандомизация во избежание худшего случая Крупные массивы без большого количества дубликатов, параллельная сортировка
Слиянием O(n·log n) «Разделяй и властвуй», объединение, внешняя сортировка Крупные массивы с неиз- вестным распределением, большие объемы данных, параллельная сортировка
Подсчетом O(n + m) Счет Крупные массивы с достаточно единообразным распределением значений

Делаем случайный порядок у массива

Чтобы перетасовать элементы в массиве нам нужно, чтобы возвращал <0, 0 или >0 рандомно, независимо от того, что выдаст a и b. Вот небольшой трюк с этим делом:

//Рандомный порядок в массиве:var myarray=  myarray.sort(function(){     return 0.5 — Math.random()}) //Теперь элементы перемешаны

Как вы видите у есть тайные стороны. На самом деле, вы даже можете сортировать массивы, которые содержат не только примитивы, а объекты со свойствами. Давайте рассмотрим этот вариант:

Сортируем массив объектов

Сейчас мы пойдем дальше и предположим, что ваш массив содержит не только простые численные или строковые значения, а вместо них объекты со свойствами:

var employees=[]employees={name: "George", age: 32, retiredate: "March 12, 2014"}employees={name: "Edward", age: 17, retiredate: "June 2, 2023"}employees={name: "Christine", age: 58, retiredate: "December 20, 2036"}employees={name: "Sarah", age: 62, retiredate: "April 30, 2020"}

Массив — это массив, состоящий из объектов со свойствами разного типа, от строк, чисел до дат (в данном случае строка с датой). Метод можно использовать для сортировки массива, основываясь на значениях одного из свойств, например сортировке по имени, возрасту и в нашем случае, даже дате выхода на пенсию. В общем, тут идея довольно простая, вам нужно изменить функцию сравнения таким образом, что она сравнивала требуемые значения свойств. Давайте посмотрим как это работает.

РЕКУРСИВНЫЕ АЛГОРИТМЫ

Встречаются такие случаи, когда задача разбивается на подзадачи, которые в свою очередь имеют ту же структуру, что и основная задача.

В таких случаях используют механизм, который называется рекурсией.

Способ вызова подпрограммы, в котором подпрограмма вызывает сама себя, называют рекурсией.

Подпрограммы, реализующие рекурсию, называются рекурсивными подпрограммами.

Поясним механизм рекурсивных подпрограмм с помощью классического примера использования рекурсии.

Пример 1.

Вычисление факториала числа.

Обоснование выбора способа реализации.

Обратим внимание на то, чтовычислить факториал числа N можно следующим образом:

N! = N * (N-1)! = N * (N-1) * (N-2)! и так далее

Реализуем такой алгоритм с использованием механизма рекурсии.

Так как подпрограмма будет производить вычисление значения, то реализовывать ее будем в виде функции.

function Fact (n: byte) : integer;

begin

if n = 0thenFact := 1

elseFact := n * Fact(n-1);

end;


Косвенная рекурсия

Описанный выше механизм часто называют прямой рекурсии.

Существует еще один рекурсивный механизм —косвенная рекурсия.

Механизм применяется для реализации следующей ситуации.

Первая подпрограмма вызывает вторую, еще не описанную.

Продемонстрируем ситуацию на примере.

Program Kosv_Rec;

……

procedure A (var x: real);

begin

….

B(z);

end;

procedure B (var y: real);

begin

A(z);

end;

Здесь процедура А обращается к процедуре B и наоборот. Какую процедуру первой мы бы ни описали, в любом случае будет ошибка – обращение к еще не описанной процедуре.

Для того, чтобы избежать такой ситуации, используется предварительное описание подпрограмм.

Предварительное описание состоит из заголовка подпрограммы и директивы (указания компилятору) предварительного описания подпрограмм FORWARD.

Позже подпрограмма описывается без повторения списка параметров и типа возвращаемого результата.

Правильная реализация вышеприведенного примера будет выглядеть следующим образом.

Program Kosv_Rec;

……

procedure B (var y: real); Forward;

procedure A (var x: real);

begin

….

B(z);


end;

procedure B;

begin

A(z);

end;

Пример 2. Быстрая сортировка.

Procedure QuickSort;

Procedure Sort (L, R: byte);

Var i, j: byte;

work, x: <тип элементов>;

begin

i:=L;j:=R;

x:= A;

repeat

while A < x do i:=i+1 end;

while x < A do j:=j-1 end;

ifi <= jthen begin

work:= A;

A:= A;

A:= work;

i:=i+1;

j:= j – 1

end;

until i > j;

if L < j then sort(L, j);

if I < R then sort I, R)


end;

Begin

Sort (1, n);

End;

Сортировка по имени

В наши дни сортировка по возрасту сотрудника может выглядеть довольно бесчувственной и некорректной, так что давайте отсортируем по именам сотрудников в возрастающем порядке. Вспомните, что по-дефолту, сортировка массива, который содержит примитивы, такие как строки, происходит в алфавитном порядке. Что говорит о том, что вам просто надо вызвать метод, без любой функции сравнения, в общем просто . Это не работает, так как данные по которым мы хотим отсортировать не являются массивом. Так что же делать? Фокус тут в том, чтобы вручную написать функцию сравнения, которая отсортирует массив по-алфавиту, что в свою очередь даст нам указать где находятся данные строк. Давайте посмотрим:

employees.sort(function(a, b){var nameA=a.name.toLowerCase(), nameB=b.name.toLowerCase()if (nameA < nameB) //сортируем строки по возрастанию  return -1if (nameA > nameB)  return 1return 0 // Никакой сортировки})

Это отсортирует массив employees по именам в возрастающем порядке, так что теперь это Christine, это Edward и так далее. Тут мы сравниваем две строки a.name с b.name и возвращаем -1, 1 или 0, в соответствии с сортировкой, точно определенной формулой, которую использует сам , без передачи какой-либо другой функции. Как вы уже наверное выяснили, в JavaScript вы можете без сомнений сравнивать две строки.

Поиск максимального элемента в массиве

Дан массив X, состоящий из n элементов. Найти максимальный элемент массива и номер, под которым он хранится в массиве.

Алгоритм решения задачи следующий. Пусть в переменной с именем Max хранится значение максимального элемента, а в переменной Nmax — его номер. Предположим, что нулевой элемент массива является максимальным и запишем его в переменную Max, а в Nmax — его номер (ноль). Затем все элементы начиная с первого сравниваем в цикле с максимальным. Если текущий элемент массива оказывается больше максимального, то записываем его в переменную Max, а в переменную Nmax — текущее значение индекса i.

Все выше описанное можно представить следующим фрагментом кода:

C++

for (Max=X, Nmax=0, i=0; i<n; i++) if (Max<X) { Max=X; Nmax=i; } cout<<«Max=»<<Max<<«\n»; cout<<«Nmax=»<<Nmax<<«\n»;

1 2 3 4 5 6 7 8

for(Max=X,Nmax=,i=;i<n;i++)

if(Max<Xi)

{

Max=Xi;

Nmax=i;

}

cout<<«Max=»<<Max<<«\n»;

cout<<«Nmax=»<<Nmax<<«\n»;

Алгоритм поиска минимального элемента в массиве будет отличаться лишь тем, что в конструкции if знак поменяется с < на >.

Передаём функцию в array.sort()

Как говорилось выше, допускает дополнительные параметры в виде функций (давайте назовем её ). Формат такой функции будет выглядеть таким образом:

function sortfunction(a, b){//Тут можно сказать, что сравнивается a и b, и возвращается -1, 0 или 1.}array.sort(sortfunction)

Когда такая функция передаётся в , элементы массива сортируются, основываясь на взаимосвязи между каждой парой элементов и и значением, отдаваемым функцией. Есть три возможных числа, которые отдадутся функцией:<0 (меньше нуля), 0, >0 (больше нуля).

В первом случае, когда меньше нуля, отсортируется с индексом меньшими, чем .

При нуле: и будут рассматриваться как равные и сортировка производиться не будет.

Больше нуля: Сортировка будет меньшего индекса, чем .

То есть, для того, чтобы сортировка прошла по числам и в возрастающем порядке, функция-параметр должна быть такой:

function sortfunction(a, b){  return (a — b)}

Дальше больше.

Сортируем массив в числовом порядке

Чтобы отсортировать массив в числовом порядке, просто передайте к , а затем возвратите разницу между и , оба параметра автоматически отправятся в функцию:

var myarray=myarray.sort(function(a,b){   return a — b}) //Массив будет 

Это работает так, как и должно работать, так как всякий раз когда меньше, чем , возвращается негативное значение, что ведет к тому, что меньший элемент всегда будет выставляться левее большего, а другими словами, порядок будет выстроен по возрастанию

Обратите внимание на то, что мы определили нашу функцию сортировки прямо внутри , как анонимную, вместо того, чтобы создавать отдельную функцию и передавать ещё в — оба варианта выдадут одинаковый результат

Сортировка массива в числовом порядке, но по убывающей, отличается не многим и всего лишь требует реверса двух операндов и :

var myarray=myarray.sort(function(a,b){   return b — a}) //Массив становится 

С этим читают