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

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

Так что же такое алгоритм?

Проще говоря, алгоритм - это серия содержащихся в нем шагов, которым вы следуете, чтобы достичь какой-то цели или произвести какой-то результат. Возьмем, к примеру, бабушкин рецепт выпечки торта. Подождите, это считается алгоритмом? Конечно!

function BakeCake(flavor, icing){
"
 1. Heat Oven to 350 F
 2. Mix flour, baking powder, salt
 3. Beat butter and sugar until fluffy
 4. Add eggs.
 5. Mix in flour, baking powder, salt
 6. Add milk and " + flavor + "
 7. Mix further
 8. Put in pan
 9. Bake for 30 minutes
10." + if(icing === true) return 'add icing' + "
10. Stuff your face
"
}
BakeCake('vanilla', true) => deliciousness

Алгоритмы полезны в нашем исследовании временной сложности, потому что они бывают самых разных форм и размеров.

Точно так же, как вы можете разрезать пирог 100 разными способами, вы можете решить одну задачу с помощью множества различных алгоритмов. Некоторые решения просто более эффективны, занимают меньше времени и места, чем другие.

Итак, главный вопрос: как нам проанализировать, какие решения наиболее эффективны?

Математика спешит на помощь! Анализ временной сложности в программировании - это просто чрезвычайно упрощенный математический способ анализа того, сколько времени потребуется алгоритму с заданным числом входов (n) для выполнения своей задачи. Обычно его определяют с помощью нотации Big-O.

Вы спросите, что такое нотация Big O?

Если вы пообещаете, что не сдадитесь и перестанете читать, я вам скажу.

Нотация Big-O - это способ преобразования общих шагов алгоритма в алгебраические термины с последующим исключением констант и коэффициентов более низкого порядка, которые не имеют такого большого влияния на общую сложность проблемы.

Математики, вероятно, будут немного недовольны моим предположением об «общем влиянии», но разработчикам, чтобы сэкономить время, проще упростить вещи следующим образом:

Regular       Big-O
2             O(1)   --> It's just a constant number
2n + 10       O(n)   --> n has the largest effect
5n^2          O(n^2) --> n^2 has the largest effect

Короче говоря, весь этот пример говорит следующее: мы смотрим только на тот фактор в нашем выражении, который потенциально имеет наибольшее влияние на значение, возвращаемое нашим выражением. (Это меняется по мере того, как константа становится очень большой, а n становится меньше, но пока не будем об этом беспокоиться).

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

  • O (1) - Постоянное время: при вводе размера n алгоритму требуется всего один шаг для выполнения задачи.
  • O (log n) - логарифмическое время: при вводе размера n количество шагов, необходимых для выполнения задачи, уменьшается на некоторый коэффициент с каждым шагом.
  • O (n) - линейное время: при вводе размера n количество требуемых шагов напрямую связано (от 1 до 1)
  • O (n²) - квадратичное время: при вводе размера n количество шагов, необходимых для выполнения задачи, равно квадрату n.
  • O (C ^ n) - экспоненциальное время: при вводе размера n количество шагов, необходимых для выполнения задачи, является константой в степени n (довольно большое число).

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

let n = 16;
O (1) = 1 step "(awesome!)"
O (log n) = 4 steps  "(awesome!)" -- assumed base 2
O (n) = 16 steps "(pretty good!)"
O(n^2) = 256 steps "(uhh..we can work with this?)"
O(2^n) = 65,536 steps "(...)"

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

Итак, как нам анализировать наш код с помощью нотации Big-O?

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

В качестве примеров мы будем использовать приведенные ниже структуры данных:

var friends = {
 'Mark' : true,
 'Amy' : true,
 'Carl' : false,
 'Ray' :  true,
'Laura' : false,
}
var sortedAges = [22, 24, 27, 29, 31]

O (1) - постоянное время

Поиск значений, когда вы знаете, что ключ (объекты) или индекс (массивы) всегда занимают один шаг и, следовательно, являются постоянным временем.

//If I know the persons name, I only have to take one step to check:
function isFriend(name){ //similar to knowing the index in an Array 
  return friends[name]; 
};
isFriend('Mark') // returns True and only took one step
function add(num1,num2){ // I have two numbers, takes one step to return the value
 return num1 + num2
}

O (log n) - логарифмическое время

Если вы знаете, на какой стороне массива искать предмет, вы экономите время, вырезая вторую половину.

//You decrease the amount of work you have to do with each step
function thisOld(num, array){
  var midPoint = Math.floor( array.length /2 );
  if( array[midPoint] === num) return true;
  if( array[midPoint] < num ) --> only look at second half of the array
  if( array[midpoint] > num ) --> only look at first half of the array
  //recursively repeat until you arrive at your solution
  
}
thisOld(29, sortedAges) // returns true 
//Notes
 //There are a bunch of other checks that should go into this example for it to be truly functional, but not necessary for this explanation.
 //This solution works because our Array is sorted
 //Recursive solutions are often logarithmic
 //We'll get into recursion in another post!

O (n) - линейное время

Вы должны просмотреть каждый элемент в массиве или списке, чтобы выполнить задачу. Одиночные циклы for почти всегда представляют собой линейное время. Также методы массива, такие как indexOf, также являются линейными по времени. Вы просто отвлечены от процесса зацикливания.

//The number of steps you take is directly correlated to the your input size
function addAges(array){
  var sum = 0;
  for (let i=0 ; i < array.length; i++){  //has to go through each value
    sum += array[i]
  }
 return sum;
}
addAges(sortedAges) //133

O (n²) - квадратичное время

Вложенные циклы for являются квадратичным временем, потому что вы выполняете линейную операцию внутри другой линейной операции (или n * n = n²).

//The number of steps you take is your input size squared
function addedAges(array){
  var addedAge = [];
    for (let i=0 ; i < array.length; i++){ //has to go through each value
      for(let j=i+1 ; j < array.length ; j++){ //and go through them again
        addedAge.push(array[i] + array[j]);
      }
    }
  return addedAge;
}
addedAges(sortedAges); //[ 46, 49, 51, 53, 51, 53, 55, 56, 58, 60 ]
//Notes
 //Nested for loops. If one for loop is linear time (n)
 //Then two nested for loops are (n * n) or (n^2) Quadratic!

O (2 ^ n) - экспоненциальное время

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

//The number of steps it takes to accomplish a task is a constant to the n power
//Thought example
 //Trying to find every combination of letters for a password of length n

Вы должны проводить анализ временной сложности каждый раз, когда пишете код, который должен работать быстро.

Когда у вас есть разные пути решения проблемы, определенно разумнее сначала создать решение, которое просто работает. Но в конечном итоге вам понадобится решение, которое будет работать как можно быстрее и эффективнее.

Вот несколько простых вопросов, которые помогут вам в решении проблемы:

1. Решает ли это проблему? Да = ›

2. У вас есть время поработать над этим

Да = ›переходите к шагу 3

Нет = ›Вернитесь к этому позже, а пока переходите к шагу 6.

3. Он охватывает все крайние случаи? Да = ›

4. Сложны ли мои сложности как можно меньше?

Нет = ›переписать или преобразовать в новое решение -› вернитесь к шагу 1

Да = ›переходите к шагу 5

5. Мой код D.R.Y? Да = ›

6. Радуйтесь!

Нет = ›Сделайте это D.R.Y и радуйтесь!

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

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

Вы можете принимать решения, использовать ли наборы или графики для хранения данных. Вы можете решить, использовать ли Angular, React или Backbone для командного проекта. Все эти решения решают одну и ту же проблему по-разному.

Учитывая это, трудно сказать, что существует единственный «правильный» или «лучший» ответ на эти проблемы. Но можно сказать, что есть «лучшие» или «худшие» ответы на данную проблему.

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

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

Короче говоря, если вы собираетесь решить проблему, решайте ее хорошо. И используйте немного Big-O, чтобы понять, как это сделать.

Вот последнее резюме:

  • O (1) - Постоянное время: алгоритм выполняет задачу всего за один шаг.
  • O (log n) - логарифмическое время: количество шагов, необходимых для выполнения задачи, уменьшается с каждым шагом в некоторый раз.
  • O (n) - Linear Time: количество необходимых шагов напрямую связано (1 к 1).
  • O (n²) - квадратичное время: количество шагов, необходимых для выполнения задачи, равно квадрату n.
  • O (C ^ n) - экспоненциальный: количество шагов, необходимых для выполнения задачи, является константой в степени n (довольно большое число).

А вот несколько полезных ресурсов, чтобы узнать больше:

  • Википедия
  • Big O Cheat Sheet - отличный ресурс с обычными алгоритмическими временными сложностями и графическим представлением. Проверьте это!