Перевод статьи «Algorithm’s Efficiency | Big O “In Simple English”».
Начнем с забавной истории.
Родом я из Демократической Республики Конго в Центральной Африке. У нас там очень низкая скорость интернет-связи. Например, при открытии Gmail загрузка может занимать от 3 до 5 минут (порой процесс прерывается по time out).
В 2009 году подобная проблема со скоростью интернета была у одной компании в Южной Африке. У этой компании было два офиса в 50 милях друг от друга. Сотрудники решили провести занимательный эксперимент и посмотреть, не будет ли быстрее пересылать данные при помощи голубиной почты.
Они поместили 4GB данных на флешку, прикрепили ее к голубю и выпустили его из офиса, чтобы он полетел в другой офис. И…
Почтовый голубь оказался быстрее интернет-связи. Он победил с большим отрывом (иначе история не была бы такой забавной). Больше того, когда голубь долетел до второго офиса, а случилось это через два часа, через интернет загрузилось только 4% данных.
Сложность. Анализ времени работы. Нотация большого «О»
В программировании нотация большого «О» (О-нотация) используется в качестве меры измерения, помогающей программистам оценивать или предполагать эффективность написанного блока кода, скрипта или алгоритма. «Сколько времени потребуется на работу этого кода? Какова его сложность в привязке к тем данным, которые он обрабатывает?»
Точное время работы скрипта или алгоритма определить сложно. Оно зависит от многих факторов, например, от скорости процессора и прочих характеристик компьютера, на котором запускается этот скрипт или алгоритм. Поэтому нотация большого «О» используется не для оценки конкретного времени работы кода. Ее используют для оценки того, как быстро возрастает время обработки данных алгоритмом в привязке к объему этих данных.
Временная и пространственная сложность
Когда вы пишете код — любой код, на любом языке программирования — вы имеете дело с двумя видами сложности: временной и пространственной.
- Временная сложность алгоритма определяет число шагов, которые должен предпринять алгоритм, в зависимости от объема входящих данных (n).
- Пространственная сложность алгоритма определяет количество памяти, которое потребуется занять для работы алгоритма, в зависимости от объема входящих данных (n).
Постоянное время: O(1)
Обратите внимание, что в истории с голубем, рассказанной выше, голубь доставил бы и 5KB, и 10MB, и 2TB данных, хранящихся на флешке, за совершенно одинаковое количество времени. Время, необходимое голубю для переноса данных из одного офиса в другой, это просто время, необходимое, чтобы пролететь 50 миль.
Если использовать О-нотацию, время, за которое голубь может доставить данные из офиса А в офис Б, называется постоянным временем и записывается как O(1). Оно не зависит от объема входящих данных.
Вот пример кода JavaScript с временной сложностью O(1):
// get the lenght of an array list
var fruits = ["Banana", "Orange", "Apple", "Mango"];
var numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
function getListLenght(list) {
var _lenght = list.length;
return _lenght;
}
console.log('The number of item in list is: ', getListLenght(fruits)); // 4
console.log('The number of item in list is: ', getListLenght(numbers)); // 14
// **********************************************************************************
// - In this case the run time of getListLenght is costant: O(1)
// - It'll take the same time to run no matter the number of item in the array list
// **********************************************************************************
Линейное время: O(n)
В отличие от пересылки голубем, передача данных через интернет будет занимать все больше и больше времени по мере увеличения объема передаваемых данных.
Если использовать О-нотацию, мы можем сказать, что время, нужное для передачи данных из офиса А в офис Б через интернет, возрастает линейно и прямо пропорционально количеству передаваемых данных. Это время записывается как O(n), где n — количество данных, которое нужно передать.
Следует учитывать, что в программировании «О» большое описывает наихудший сценарий. Допустим, у нас есть массив чисел, где мы должны найти какое-то определенное число при помощи цикла for. Оно может быть найдено при любой итерации, и чем раньше, тем быстрее функция завершит работу. О-нотация всегда указывает на верхнюю границу, т. е., описывает случай, когда алгоритму придется осуществить максимальное количество итераций, чтобы найти искомое число. Как, например, в том случае, если это число окажется последним в перебираемом массиве.
Вот пример кода на JavaScript с временной сложностью O(n):
// return true if an item exists in list
// and false if it doesn't
var fruits = ["Banana", "Orange", "Apple", "Mango"];
var numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14];
function checkItemInList(item, list) {
return list.includes(item);
}
console.log('Is Mango in Fruit List:', checkItemInList('Mango', fruits)); // true
console.log('Is Avocado in Fruit List:', checkItemInList('Avocado', fruits)); // false
console.log('Is 14 in numbers list:', checkItemInList(14, numbers)); // true
console.log('Is 15 in numbers list:', checkItemInList(15, numbers)); // false
// **********************************************************************************
// - In the case the run time of checkItemInList is O(n)
// - n being the number of item in the array list
// - Big O Notaion favor the worse case scenaior: the item we are looking for
// - is the last item in the list array
// **********************************************************************************
Квадратичное время: O(n2)
Квадратичное время представляет алгоритм, производительность которого прямо пропорциональна квадрату размера входящих данных.
Распространенный пример такого алгоритма — два вложенных цикла. По мере увеличения вложенности растет и временная сложность (O(n³), O(n⁴) и т. д.).
// read an array of array
function readArrayOfArray() {
// This is an array of arrays.
// It is a little easier to read like this:
var arrayNumberFruit = [
[1, 'Orange'],
[2, 'Banana'],
[3, 'Apple'],
[4, 'Mango']
];
arrayNumberFruit.forEach(function (items) {
// will display [1, 'Orange'], [2, 'Banana'],...
console.log('Items in the array are: ', items);
items.forEach(function (number) {
// will display 1, Orange, 2, Banana, 3 ......
console.log('Numbers in the array are: ', number); //
});
});
}
// **********************************************************************************
// - In this case the run time of readArrayOfArray is quadratic: O( n²)
// - the method goes as O(N*N) or O(N²), because every time you increase the number
// - of items in the array of array, the computation effort or time will increase as
// - the square of the number of points.
// **********************************************************************************
Экспоненциальное время: O(2^n)
Если сложность алгоритма описывается формулой O(2^n), значит, время его работы удваивается с каждым дополнением к набору данных. Кривая роста функции O(2^n) экспоненциальная: сначала она очень пологая, а затем стремительно поднимается вверх. Примером алгоритма с экспоненциальной сложностью может послужить рекурсивный расчет чисел Фибоначчи:
// recursive calculation of Fibonacci numbers
function fibonacci(number) {
if (number <= 1) return number;
return fibonacci(number - 2) + fibonacci(number - 1);
}
console.log(fibonacci(5));
console.log(fibonacci(6));
console.log(fibonacci(7));
// **********************************************************************************
// - In this case the run time of readArrayOfArray is quadratic: O(2^N)
// **********************************************************************************
Логарифмическое время: O(log n)
Логарифмическое время поначалу понять сложнее. Поэтому для объяснения я воспользуюсь распространенным примером: концепцией бинарного поиска.
Бинарный поиск это алгоритм поиска в отсортированных массивах. Работает он следующим образом. В отсортированном наборе данных выбирается серединный элемент и сравнивается с искомым значением. Если значение совпадает, поиск завершен.
Если искомое значение больше, чем значение серединного элемента, нижняя половина набора данных (все элементы с меньшими значениями, чем у нашего серединного элемента) отбрасывается и дальнейший поиск ведется тем же способом в верхней половине.
Если искомое значение меньше, чем значение серединного элемента, дальнейший поиск ведется в нижней половине набора данных.
Эти шаги повторяются, при каждой итерации отбрасывая половину элементов, пока не будет найдено искомое значение или пока оставшийся набор данных станет невозможно разделить напополам:
// Binary Search(Iterative Approach)
var binarySearch = function (array, number) {
var start = 0;
var end = array.length - 1;
// Iterate while start not meets end
while (start <= end) {
// Find the mid index
var mid = Math.floor((start + end) / 2);
// If element is present at mid, return True
if (array[mid] === number) return true;
// Else look in left or right half accordingly
else if (array[mid] < number)
start = mid + 1;
else
end = mid - 1;
}
return false;
};
function findNumber(array, number) {
if (binarySearch(array, number, 0, array.length-1)) {
return('Number 5 exist in the array');
} else {
return('Number 5 not found!');
}
}
var numberArray = [1, 3, 4, 2, 5, 7, 6, 8, 9];
var searched_number = 5;
// will display Number 5 exist in the array
console.log(findNumber(numberArray, searched_number));
// **********************************************************************************
// - In this case the run time of this script is: O(logn)
// - this is a script that implement binary search through iterative approach.
// - we use a while loop, which runs until it hits the base condition
// - i.e start becomes greater than end.
// - best case scenario is when the element we are looking for is stored in the
// - middle of the array.(which means the script will only run one time)
// - Worst case scenario is when the element we are looking for is stored either
// - at the end or begining of the array
// **********************************************************************************
Вот обычный порядок возрастания времени:
- O(1) — постоянное время
- O(log n) — логарифмическое время
- O(n) — линейное время
- O(n²) — квадратичное время
- O(2^n) — экспоненциальное время
- O(n!) — факториальное время
Если вы начинающий программист, старайтесь выработать у себя привычку учитывать временную и пространственную сложность при проектировании алгоритмов и написании кода. Это позволит вам оптимизировать ваш код и сразу же решить все потенциальные проблемы с производительностью.
«Писать код это хорошо, писать работающий код еще лучше, но лучше всего писать оптимизированный работающий код».
Довольно очевидно, что скрипт, обрабатывающий данные за 2 минуты, лучше скрипта, который делает все то же самое, но за 5 минут. Писать рабочий код, легкий для понимания и удовлетворяющий все требования по части функционала это дело хорошее, но на это способен любой программист. А вот оптимизированный код (эффективный и по времени, и по ресурсоемкости), с хорошим балансом читаемости, времени работы и поддерживаемости пишут уже настоящие разработчики.
[customscript]techrocks_custom_after_post_html[/customscript]
[customscript]techrocks_custom_script[/customscript]