Этот блог предназначен для разработчиков программного обеспечения, которые хотят расширить свои знания об алгоритмах и временной сложности, а также понять, как и когда использовать метод пузырьковой сортировки.
Вас, как разработчика программного обеспечения, БУДЕТ иногда просить вычислить временную сложность алгоритма или программы. Вас даже могут попросить самостоятельно написать алгоритм с определенной временной сложностью. На многих технических собеседованиях, которые вы проходите, если не на всех, вам будут задавать эти вопросы.
Впервые я столкнулся с этими графами и алогрифмическими задачами во время учебы в Школе разработки программного обеспечения Flatiron. Я не думал, что они будут так важны для понимания, пока не дойду до конца программы, где я узнал, что мне может понадобиться решить эти проблемы во время технического собеседования. Возможно, вам не нужно знать о них все, но понимание этих проблем и наличие плана их решения выделит вас среди других кандидатов, с которыми вы сталкиваетесь.
Что такое временная сложность?
Проще говоря, временная сложность — это эффективность программы или время, необходимое программе для выполнения своей задачи. Как вы видели на графике выше, временная сложность выражается в «большой нотации О». Математическое представление алгоритма записывается как O(Nn). «N» — это количество входных данных, а «n» — это количество циклических выражений. Я рассмотрю некоторые из этих временных сложностей с некоторыми примерами ниже.
Пузырьковая сортировка
Получив массив чисел, как бы вы отсортировали этот массив, чтобы он сортировался от наименьшего числа к наибольшему? Ну, как новичок в сортировке, я бы попытался создать функцию, которая будет проверять первый элемент массива и проверять, больше ли это число, чем следующий элемент, а затем менять местами индексы, если этот первый элемент больше, чем второй элемент и продолжайте этот процесс до тех пор, пока массив не будет отсортирован. По сути, это и есть пузырьковая сортировка. Пузырьковая сортировка выполняется путем сравнения соседних элементов и их сортировки в порядке возрастания или убывания. Вот пример ниже:
let arr = [2, 4, 3, 5, 1] function bubbleSort(arr){for(let i = 0; i < arr.length; i++){for(letj = 0; j < ( arr.length - i -1 ); j++){if(arr[j] > arr[j+1]){ lettemp = arr[j] arr[j] = arr[j + 1] arr[j+1] = temp } } } console.log(arr); }// expected output ===> [1, 2, 3, 4, 5]
В этом примере кода мы проверяем, больше ли элемент на текущей итерации, чем на следующей итерации. Если это окажется правдой, то мы поменяем эти элементы местами и двинемся дальше. Касаясь временной сложности этой функции, поскольку этот массив содержит пять элементов, вы будете выполнять четыре сравнения.
N = Number of elements in array N - 1 = Number of time comparisons that occur 5 - 1 = 4
Этот пример имеет временную сложность O(n²), что означает, что это не самое оптимизированное решение для сортировки массива. Если бы массив уже был отсортирован, то временная сложность была бы O(n), что, очевидно, является самым быстрым решением для проверки того, отсортирован ли массив.
Сортировка выбора
Метод сортировки более прост для понимания, поскольку делит массив на две части: отсортированную и несортированную. Это означает, что пока этот алгоритм работает, он проверяет, какая сторона отсортирована, а какая несортированная, и просто отсортировывает несортированную сторону! Для несортированной стороны он проверит наименьшее число и поместит его в отсортированную сторону. Затем на следующей итерации он сделает то же самое и снова проверит наименьшее число в несортированной части, переместит его в отсортированную сторону и так далее… Вот пример того, что происходит под капотом.
Это первая итерация того, как он сортирует несортированную часть массива. Как только элемент с наименьшим значением найден после итерации по всей стороне несортированного массива, он помещает это значение в отсортированную сторону. На этот раз сложность такая же, как у пузырьковой сортировки со значением O(n²), но немного проще понять, как она работает. Пример кода для этого приведен ниже:
function selectionSort(inputArr) {
let n = inputArr.length;
for(let i = 0; i < n; i++) {
// Finding the smallest number in the unsorted array
let min = i;
for(let j = i+1; j < n; j++){
if(inputArr[j] < inputArr[min]) {
min=j;
}
}
if (min != i) {
// Swapping the elements
let tmp = inputArr[i];
inputArr[i] = inputArr[min];
inputArr[min] = tmp;
}
}
return inputArr;
}
Сортировка слиянием
Сортировка слиянием — один из наиболее популярных алгоритмов сортировки массивов из-за временной сложности и эффективности этого метода. Временная сложность составляет O(n*logn), что означает, что операции logn будут выполняться n раз. Это очень распространенный алгоритм многих разработчиков. Сортировка слиянием делит заданный массив пополам, а затем делает это до тех пор, пока каждый элемент не станет отдельным подмассивом. Ниже приведен пример того, как это работает:
После разделения массива на подмассивы, которые можно сортировать, процесс слияния затем объединяет эти массивы в отсортированный массив, а затем продолжает объединять их в окончательный отсортированный массив. Пример того, как будет выглядеть код, приведен ниже:
function merge(left, right) {
let arr = []
// Break out of loop if any one of the array gets empty
while (left.length && right.length) {
// Pick the smallest element of left and right sub arrays
if (left[0] < right[0]) {
arr.push(left.shift())
} else {
arr.push(right.shift())
}
}
return [ ...arr, ...left, ...right ]
}
Краткое содержание
Надеюсь, это поможет понять некоторые алгоритмы сортировки для вашего будущего и теперь вы сможете решить любую проблему, связанную с этими типами методов, когда вы столкнетесь с ними. Они будут очень полезны для понимания временной сложности этих алгоритмов, а также пригодятся для вашего технического собеседования!
