Перерыв на кофе ознакомление с временной сложностью алгоритмов

1656606033 pereryv na kofe oznakomlenie s vremennoj slozhnostyu algoritmov

Так же, как писать свой первый for цикл, понимание временной сложности является неотъемлемой вехой для обучения написанию эффективных сложных программ. Думайте об этом как о сверхспособности, позволяющей вам точно знать, какой тип программы может быть наиболее эффективным в конкретной ситуации – еще до того, как запустить одну строку кода.

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

Чтобы начать писать более эффективные программы, вам не потребуется много времени — мы можем сделать это примерно через пятнадцать минут. Ты можешь пойти выпить кофе прямо сейчас (или чая, если это твое желание), и я расскажу тебя до того, как кончится твой кофе-пауза. Давай, я подожду.

Все готово? Давайте сделаем это!

Что такое «временная сложность»?

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

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

Мы описываем эффективность алгоритма увеличения размера его входных данных, п. Если входная строка, то п — длина строчки. Если это список целых чисел, п является длиной списка.

Проще представить, что обозначает большое О с помощью графика:

05O9lIJ7IskYF05LomQMNSdgLSxE4qhY3xef
Линии, созданные с помощью очень хорошего калькулятора графиков Desmos. Вы можете поиграть с этим графиком здесь.

Вот основные важные моменты, которые следует помнить, читая остальную часть этой статьи:

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

Определение временной сложности

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

Полиномиальная временная сложность

А полиномот греч поле означает «много» и лат номен что означает «имя», описывает выражение, состоящее из константных переменных, а также добавление, умножение и подъем к неотъемлемой целой степени. Это суперматематический способ сказать, что он содержит переменные, обычно обозначаемые буквами, и символы, которые выглядят так:

dzjaOr9FE89dYVE5ZlQ5Ddb28xOGZT3vQ8La

Нижеследующие классы описывают полиномиальные алгоритмы. У некоторых есть примеры пищи.

Постоянный

А постоянное время Алгоритм не изменяет свое время работы в ответ на входящие данные. Независимо от получаемых им данных, для выполнения алгоритма требуется одинаковое количество времени. Обозначим это как временную сложность О(1).

xgqMQNEOKLYBDBCXNQ4RJBhTUMwKVTgMOt4K

Вот один пример постоянного алгоритма, принимающего первый элемент в срезе.

func takeCupcake(cupcakes []int) int {
	return cupcakes[0]
}
5Ypub2bQrF6lf4s20VkNpK178mhMLZTNOGZP
Выбор вкусов: ванильный кекс, клубничный кекс, мятно-шоколадный кекс, лимонный кекс и кекс Wibbly wabbly, timey wimey.

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

Линейный

Продолжительность запуска a линейный алгоритм постоянный. Он обработает ввод п количество сделок. Часто это самый лучший (самый эффективный) случай для временной сложности, когда все данные должны быть проверены.

EZDOxe5ylKG0rg0H3YRAlTwXp-htTL3RF1pj

Вот пример кода с временной сложностью О(п):

func eatChips(bowlOfChips int) {
	for chip := 0; chip <= bowlOfChips; chip++ {
		// dip chip
	}
}

Вот еще один пример кода с временной сложностью О(п):

func eatChips(bowlOfChips int) {
	for chip := 0; chip <= bowlOfChips; chip++ {
		// double dip chip
	}
}

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

c2mTyNEzt4zCa1lqqlOjxSgFyYpxPBDy7oRH
Не погружайте дважды в общую миску.

Квадратный

AAOdoTdm2s3fuBxrIw9w1r4iGv9xMs3MFXRy

Теперь вот пример кода с временной сложностью О(п2):

func pizzaDelivery(pizzas int) {
	for pizza := 0; pizza <= pizzas; pizza++ {
		// slice pizza
		for slice := 0; slice <= pizza; slice++ {
			// eat slice of pizza
		}
	}
}

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

кубический

gCSUwDt1nmJSrTicLxlldqXdH9F0zIHurMN8

Расширяя предыдущий пример, этот код с тремя вложенными циклами имеет временную сложность. О(п3):

func pizzaDelivery(boxesDelivered int) {
	for pizzaBox := 0; pizzaBox <= boxesDelivered; pizzaBox++ {
		// open box
		for pizza := 0; pizza <= pizzaBox; pizza++ {
			// slice pizza
			for slice := 0; slice <= pizza; slice++ {
				// eat slice of pizza
			}
		}
	}
}
f1h7-yXidgFQESdRK00WNgc-CuXwAQ0BGeGr
Если серьезно, кто доставляет нерезанную пиццу?

Логарифмический

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

EFk5xco9PMY-q6Kjv0ZcBq0Fm3PicLRY6CvO

Одним из примеров этого является алгоритм двоичного поиска, находящий позицию элемента в отсортированном массиве. Вот как это будет работать, если мы пытаемся найти элемент x:

  1. Если x соответствует среднему элементу м массива, верните позицию м.
  2. Если x не совпадает мпосмотрите, если м больше или меньше x Если больше, отбросьте все элементы массива больше м. Если меньше, отбросьте все элементы массива меньше м.
  3. Продолжайте, повторяя шаги 1 и 2 на остальном массиве, пока x находится.

Я считаю, что наиболее яркой аналогией для понимания двоичного поиска есть представление процесса поиска книги в проходе книжного магазина. Если книги упорядочены по фамилии автора и вы хотите найти «Терри Пратчетт», знайте, что вам нужно искать раздел «P».

Вы можете подойти к полке в любой момент вдоль прохода и посмотреть там фамилию автора. Если вы смотрите на книгу Нила Геймана, вы знаете, что можете игнорировать все другие книги слева, поскольку ни одна буква, стоящая перед «G» в алфавите, не является «P». Затем вы переместитесь по проходу вправо на любое количество и повторите этот процесс, пока не найдете раздел Терри Пратчетта, который должен быть достаточно значительным, если вы находитесь в любом приличном книжном магазине, потому что он написал много книг.

Quasilinear

MtnuvO9ik8A-53LShA7IabhvmsWaIpI7nAZs

Часто встречается с алгоритмами сортировки, временной сложностью. О(п журнал п) может описать структуру данных, где выполняется каждая операция О(журнал п) время. Одним из примеров этого является быстрая сортировка, алгоритм «разделяй и властвуй».

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

Неполиномиальная временная сложность

Ниже приведенные классы алгоритмов неполиномиальны.

Факторный

9qJwzt9mivXPNJ3paXniaID4t3nYVVKyfMVc

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

Экспоненциальная

An экспоненциальный Алгоритм часто также берет на себя все подмножества входных элементов. Это сказывается О(2п) и часто встречается в алгоритмах грубой силы. Он подобен факторному времени, за исключением скорости роста, которая, как вы можете не удивиться, экспоненциальна. Чем больше набор данных, тем круче становится кривая.

EypghHiSZPBip2XdnBuygTC3GeAmFeAym9EJ

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

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

Временная сложность рекурсии

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

Вот рекурсивная функция, которая ест пироги, пока не останется ни одного пирога:

func eatPies(pies int) int {
	if pies == 0 {
		return pies
	}
	return eatPies(pies - 1)
}

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

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

nTl7cFkAtXJFXY1J9pXTJ1GGuR87zhgNTO6D
Возвращаемое значение этой функции равно нулю плюс некоторые нарушения пищеварения.

В самом худшем случае сложность времени

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

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

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

package main

import "fmt"

func takeCupcake(cupcakes []int) int {
	fmt.Println("Have cupcake number",cupcakes[0])
	return cupcakes[0]
}

func eatChips(bowlOfChips int) {
	fmt.Println("Have some chips!")
	for chip := 0; chip <= bowlOfChips; chip++ {
		// dip chip
	}
	fmt.Println("No more chips.")
}

func pizzaDelivery(boxesDelivered int) {
	fmt.Println("Pizza is here!")
	for pizzaBox := 0; pizzaBox <= boxesDelivered; pizzaBox++ {
		// open box
		for pizza := 0; pizza <= pizzaBox; pizza++ {
			// slice pizza
			for slice := 0; slice <= pizza; slice++ {
				// eat slice of pizza
			}
		}
	}
	fmt.Println("Pizza is gone.")
}

func eatPies(pies int) int {
	if pies == 0 {
		fmt.Println("Someone ate all the pies!")
		return pies
	}
	fmt.Println("Eating pie...")
	return eatPies(pies - 1)
}

func main() {
	takeCupcake([]int{1, 2, 3})
	eatChips(23)
	pizzaDelivery(3)
	eatPies(3)
	fmt.Println("Food gone. Back to work!")
}

Мы можем описать временную сложность всего кода сложностью его самой сложной части. Эта программа состоит из функций, которые мы уже видели, со следующими классами сложности по времени:

azvMui-3KR6nAf4wlnKCpTelyz8F7scfqSaA

Для описания временной сложности всей программы офисной вечеринки выбираем самый плохой случай. Эта программа будет иметь временную сложность О(п3).

Вот саундтрек к офисной вечеринке, просто для развлечения.

Have cupcake number 1
Have some chips!
No more chips.
Pizza is here!
Pizza is gone.
Eating pie...
Eating pie...
Eating pie...
Someone ate all the pies!
Food gone. Back to work!

P против NP, NP-полный и NP-твердый

Вы можете встретить эти термины в своих исследованиях сложности времени. неофициально, П (для полиномиального времени) — это класс быстро решаемых задач. ЧП, для недетерминированного полиномиального времени – это класс задач, ответ которых можно быстро проверить за полиномиальное время. NP охватывает P, а также другой класс задач, называемый NP-полная, для которого неизвестно скорейшее решение. Вне NP, но все еще включает NP-complete, есть еще один класс, который называется NP-твердыйчто включает задачи, которые никому не удалось проверить с помощью полиномиальных алгоритмов.

n7lVeNIYOP0ZgGmoc8Uj5EBt6yizJQkuNnAJ
Диаграмма P против NP Эйлера, автор Бехнам Эсфахбод, CC BY-SA 3.0

P против NP – нерешенный, открытый вопрос в информатике.

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

Перед написанием кода оцените эффективность алгоритма

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

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

BLsvB66DYy8bOZokzIvje8l5Hnvq9l6M-8sw

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

Оба следующие два алгоритма имеют О(п) сложность времени.

func makeCoffee(scoops int) {
	for scoop := 0; scoop <= scoops; scoop++ {
		// add instant coffee
	}
}
func makeStrongCoffee(scoops int) {
	for scoop := 0; scoop <= 3*scoops; scoop++ {
		// add instant coffee
	}
}

Первая функция делает чашку кофе с количеством ложек, которые мы просим. Вторая функция также готовит чашку кофе, но она втрое увеличивает количество ложек, которые мы просим. Чтобы увидеть наглядный пример, попросим обе эти функции для чашки кофе с миллионом ложек.

Вот результат теста Go:

Benchmark_makeCoffee-4          1000000000             0.29 ns/op
Benchmark_makeStrongCoffee-4    1000000000             0.86 ns/op

Наша первая функция, makeCoffee, завершено в среднем за 0,29 наносекунд. Наша вторая функция, makeStrongCoffee, завершено в среднем за 0,86 наносекунд. Хотя обе эти цифры могут показаться достаточно малыми, учтите, что для приготовления более крепкого кофе понадобилось почти втрое больше времени. Это должно быть интуитивно понятно, поскольку мы попросили его утроить меру. Одно обозначение великого О не даст вам этого понять, поскольку постоянный коэффициент тройных черпаков не учитывается.

Увеличить временную сложность существующего кода

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

Скажем, куча людей в офисе хотят пирога. Некоторые люди хотят пирога больше, чем другие. Сумма, которую все хотят пирога, представлена int > 0:

diners := []int{2, 88, 87, 16, 42, 10, 34, 1, 43, 56}

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

Не сортируя список посетителей, верните три самых больших целых числа в срезе.

Вот функция, которая решает эту проблему и имеет О(п2) сложность по времени:

func giveForks(diners []int) []int {
	// make a slice to store diners who will receive forks
	var withForks []int
	// loop over three forks
	for i := 1; i <= 3; i++ {
		// variables to keep track of the highest integer and where it is
		var max, maxIndex int
		// loop over the diners slice
		for n := range diners {
			// if this integer is higher than max, update max and maxIndex
			if diners[n] > max {
				max = diners[n]
				maxIndex = n
			}
		}
		// remove the highest integer from the diners slice for the next loop
		diners = append(diners[:maxIndex], diners[maxIndex+1:]...)
		// keep track of who gets a fork
		withForks = append(withForks, max)
	}
	return withForks
}

Эта программа работает, и в конце концов возвращает посетителей [88 87 56]. Но все становятся немного нетерпеливыми, пока он работает, поскольку для того, чтобы раздать три вилки, нужно достаточно много времени (около 120 наносекунд), а пирог остынет. Как мы могли бы его улучшить?

Подумав о нашем подходе немного по-другому, мы можем переработать эту программу О(п) сложность времени:

func giveForks(diners []int) []int {
	// make a slice to store diners who will receive forks
	var withForks []int
	// create variables for each fork
	var first, second, third int
	// loop over the diners
	for i := range diners {
		// assign the forks
		if diners[i] > first {
			third = second
			second = first
			first = diners[i]
		} else if diners[i] > second {
			third = second
			second = diners[i]
		} else if diners[i] > third {
			third = diners[i]
		}
	}
	// list the final result of who gets a fork
	withForks = append(withForks, first, second, third)
	return withForks
}

Вот как работает новая программа:

Сначала закусочная 2 (первый в списке) присваивается first вилка. Остальные вилки остаются не предназначенными.

Затем обед 88 вместо этого назначается первая вилка. Закусочная 2 получает second один.

Закусочная 87 не более чем first который на данный момент есть 88но это больше чем 2 кто имеет second вилка. Итак, second вилка идет к 87. Закусочная 2 получает third вилка.

Продолжая в этом жестоком и быстром обмене вилками, закусочные 16 затем назначается third вместо вилки 2и так дальше.

Мы можем добавить оператор print к циклу, чтобы увидеть, как воспроизводятся задачи fork:

0 0 0
2 0 0
88 2 0
88 87 2
88 87 16
88 87 42
88 87 42
88 87 42
88 87 42
88 87 43
[88 87 56]

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

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

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

Источники

«Если я видел дальше, то стоял на плечах Гигантов». – Исаак Ньютон, 1675

  1. Антти Лааксон. Руководство конкурентоспособного программиста (pdf), 2017 год
  2. Википедия: обозначение великого О
  3. StackOverflow: что такое простое английское объяснение нотации Большое О?
  4. Википедия: Полином
  5. Википедия: NP-полнота
  6. Википедия: NP-твердость
  7. Калькулятор графиков Desmos

Спасибо, что прочли! Если вы нашли эту публикацию полезной, поделитесь ею с кем-то другим, кому она также может быть полезна!

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *