Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 100
Теперь я знаю, что можно печатать на обратных страницах тетрадей по информатике или в конце учебников.
Спасибо. Простая и полезная статья!
от таблицы один профит — алгоритм в мой голове «на уровне», или можно лучше?
Вам этого мало???
Научите меня? (напишите статью, как научиться в смысле). Прошел два курса, прослушал кучу лекций — я так и не понял как определяется сложность алгоритмов.
«Алгоритмы — Построение и Анализ» (Кормен, Лейзерсон, Ривест, Штайн). Часть I, главы 1-4.
Есть две отличных книги с разделами про: CLRS ака Алгоритмы: построение и анализ и Конкретная математика. В обеих книгах хорошие вводные разделы про анализ сложности.
Очень сложные книги, зачем их советовать,
Потому что они хорошо и тщательно описывают анализ сложности, а в CLRS еще и разбираются сложности для базовых структур.
Они сложные для понимания большинства студентов, педагогически для самостоятельной работы они мало приспособлены.
Увы можно было учиться по энциклопедиям будь вы правы.
Увы можно было учиться по энциклопедиям будь вы правы.
Да ладно. Как раз и Алгоритмы и Конкретная математика вполне применимы как учебник. Просто их надо использовать вдумчиво и тщательно. И задачки там не просто так даны. Я же не предлагаю Искусство программирования, вот оно уже харкорно)
Вы читали главу конкретной математики про производящии функции? И готовы дать ответ на материал в этой главе?
Я уверен что если и читали то большую часть не поняли и ответ не дадите.
Не стоит писать то в чем не разбираетесь.
Это очень сложный учебник, для одаренных студентов или специалистов, но не как не для самообучения
Я уверен что если и читали то большую часть не поняли и ответ не дадите.
Не стоит писать то в чем не разбираетесь.
Это очень сложный учебник, для одаренных студентов или специалистов, но не как не для самообучения
Ну Кормена вполне можно самому изучать, вместе с задачами. С преподавателем, разумеется, получается более эффективно (есть опыт обеих путей).
Попробуем сделать дискуссию конструктивнее: какие книги порекомендовали бы вы? :)
Интересные задачки. Выглядят вполне решаемыми, даже если не читать главу перед ними. Правда, трудно судить, насколько для решения надо быть специалистом — или достаточно просто уровня олимпиадника по математике.
«Алгоритмы и структуры данных» Н.Вирт, 360с
«Алгоритмы. Введение в разработку и анализ» ( Ананий Левитин ). Советую!
«Жемчужины программирования» (Бентли).
Как бы в 2х словах объяснить… Допустим, у нас есть некоторый счётчик. При каждой выполненной операции он увеличивается на 1.
Сложность алгоритма — это зависимость конечного значения этого счётчика от размера входных данных. Константный множитель не учитывается.
По факту — каждый вложенный цикл, цикл увеличивает сложность в n раз.
Поиск значения в упорядоченном массиве разбиением диапазонов пополам имеет сложность log n: Отрезок длинной n можно поделить пополам log2 n раз. Но так как основание логарифма можно изменить, вынеся константный множитель — основание не указывают.
Самый большой треш, что я писал имел сложность n^11 — подбор 11-ти точек под определённые условия полным перебором — лаба в универе 100 точек обрабатывались за 20-30 секунд.
Сложность алгоритма — это зависимость конечного значения этого счётчика от размера входных данных. Константный множитель не учитывается.
По факту — каждый вложенный цикл, цикл увеличивает сложность в n раз.
Поиск значения в упорядоченном массиве разбиением диапазонов пополам имеет сложность log n: Отрезок длинной n можно поделить пополам log2 n раз. Но так как основание логарифма можно изменить, вынеся константный множитель — основание не указывают.
Самый большой треш, что я писал имел сложность n^11 — подбор 11-ти точек под определённые условия полным перебором — лаба в универе 100 точек обрабатывались за 20-30 секунд.
Зачем вам статья. Это тривиальный материал который изложен в сотнях учебников. Вы же понимаете что такое циклы?
Вам надо просто напрячь голову, хотя бы минимально. Просто читая каждое предложение в учебнике не идите к следующему пока не поймете текущее.
Занудство
Меня вообще удивляет любовь людей читать книги/лекции/чтоугодно сотнями ни разу не понимая что же там написано.
Неужели не тошно самим от собственного нежелания остановиться немного, не спешить, но зато понять каждую мелочь и деталь которую хотел сказать автор?
Вам надо просто напрячь голову, хотя бы минимально. Просто читая каждое предложение в учебнике не идите к следующему пока не поймете текущее.
Занудство
Меня вообще удивляет любовь людей читать книги/лекции/чтоугодно сотнями ни разу не понимая что же там написано.
Неужели не тошно самим от собственного нежелания остановиться немного, не спешить, но зато понять каждую мелочь и деталь которую хотел сказать автор?
Это ни разу не тривиальный материал. Вот оцените амортизированную сложность в куче фиббоначи? Или в Van Emde Boas дереве. Даже в динамическом массиве не достаточно посчитать циклы/вызовы методов для того, чтобы дать амортизированную оценку сложности.
Циклы подходят только для грубой оценки сложности сверху в худшем случае.
Циклы подходят только для грубой оценки сложности сверху в худшем случае.
А меня удивляет любовь людей комментировать направо и налево вместо того, чтобы начать заполнять звенящую пустоту в голове.
Давай-ка навскидку, не заглядывая никуда, сообщи нам сложности:
5n
3n^2+2n−100
10log(n)+5n
10log(n)+5n^2
3n^3−2000n^2
2n^2
50n+nlog(n)
1000+2000000
2n+n^2
logn+1000
А также:
И еще:
Ну и вот:
Эти задания — элементарные. Для тех, кто впервые коснулся вопроса.
5n
3n^2+2n−100
10log(n)+5n
10log(n)+5n^2
3n^3−2000n^2
2n^2
50n+nlog(n)
1000+2000000
2n+n^2
logn+1000
А также:
def recurPowerNew(a, b):
print a, b
if b == 0:
return 1
elif b%2 == 0:
return recurPowerNew(a*a, b/2)
else:
return a * recurPowerNew(a, b-1)
И еще:
def unionNew(L1, L2):
'''
L1 & L2 are lists of the same length, n
'''
temp = []
for e1 in L1:
flag = False
for e2 in L2:
if e1 == e2:
flag = True
break
if not flag:
temp.append(e1)
return temp + L2
Ну и вот:
def isIn(a, s):
'''
a is a character, or, singleton string.
s is a string, sorted in alphabetical order.
'''
if len(s) == 0:
return False
elif len(s) == 1:
return a == s
else:
test = s[len(s)/2]
if test == a:
return True
elif a < test:
return isIn(a, s[:len(s)/2])
else:
return isIn(a, s[len(s)/2+1:])
Эти задания — элементарные. Для тех, кто впервые коснулся вопроса.
Что вы имеете в виду под «сообщить сложность 5n» (например)? Если алгоритм выполняет 5n шагов, то и сложность его будет как раз 5n. Так-то конечно можно догадаться, что вы спрашиваете скорее всего про точную оценку (которая обозначается большой буквой тета) с учётом только старших степеней и без константы. Иначе можно много всего напридумывать, подходящего под вопрос, скажем 5n = O(n! — 3n^2).
Ступил. Задание на самом деле не указать сложность, а выбрать из списка наиболее близкую: O(1),O(log(n)),O(n),O(nlog(n)),O(nc) or O(cn).
Чтобы посчитать сложность, надо описать количество операций для входных данных размера n и посмотреть на асимптотику на бесконечности. Алгоритм линеен — значит, ему на каждый бит входных данных потребуется (примерно) пропорциональное количество операций. Пример нелинейного алгоритма — сортировка пузырьком. Для каждого из n элементов потребуется в среднем n/2 перестановок (это реальные цифры), в результате массив из n чисел мы отсортируем за n^2 операций.
Чем это плохо: большие массивы становится отсортировать все труднее и труднее. Массив из всего 1000 чисел будет сортироваться миллион операций. Дальше — больше. Это сложность O(n^2). Математическое значение записи «f(x)=O(g(x)) при x->a» представляет собой «существует конечный предел отношения f(x)/g(x) при x->a». То есть f примерно пропорциональна g при x, близких к a.
Гораздо лучше квадратичных алгоритмов линейные — O(n). Радиксная (поразрядная) сортировка отсортирует ваш массив n интов за примерно kn (где k — постоянная) операций процессора. У меня получалось k~4. Это уже зависит от компьютера и от реализации. Главное — что в теории сортировка требует пропорциональное количество операций количеству входных данных. Милионный массив она отсортирует за, скажем, пять миллионов операций перестановок. В это же время сортировка, работающая за квадрат (то есть O(n^2)), например, пузырек, будет сортировать его миллион миллионов операций, что может занять ну очень много времени. Примерно в двести тысяч раз дольше, чем радикс в выбранных нами условиях. Дальше отрыв становится все больше.
Надеюсь, что-нибудь было полезно.
Чем это плохо: большие массивы становится отсортировать все труднее и труднее. Массив из всего 1000 чисел будет сортироваться миллион операций. Дальше — больше. Это сложность O(n^2). Математическое значение записи «f(x)=O(g(x)) при x->a» представляет собой «существует конечный предел отношения f(x)/g(x) при x->a». То есть f примерно пропорциональна g при x, близких к a.
Гораздо лучше квадратичных алгоритмов линейные — O(n). Радиксная (поразрядная) сортировка отсортирует ваш массив n интов за примерно kn (где k — постоянная) операций процессора. У меня получалось k~4. Это уже зависит от компьютера и от реализации. Главное — что в теории сортировка требует пропорциональное количество операций количеству входных данных. Милионный массив она отсортирует за, скажем, пять миллионов операций перестановок. В это же время сортировка, работающая за квадрат (то есть O(n^2)), например, пузырек, будет сортировать его миллион миллионов операций, что может занять ну очень много времени. Примерно в двести тысяч раз дольше, чем радикс в выбранных нами условиях. Дальше отрыв становится все больше.
Надеюсь, что-нибудь было полезно.
Раз уж стали приводить математические определения, то давайте делать это правильно :) А по определению математическое обозначение f(x)=O(g(x)) обозначает, что f(x) < C*g(x) в некоторой области, где C — некоторая константа.
f(x)=O(g(x)): f(x) <= C*g(x)
f(x)=o(g(x)): f(x) < C*g(x)
f(x)=o(g(x)): f(x) < C*g(x)
В вашем описании нет различия между О большое и о малое.
Нет, вы абсолютно не правы. Очевидно же, что ваше и моё определение O(..) совпадают! А следовательно, вводить ещё такое же o(..) смысла нет — на самом деле у него другое математическое определение: f=o(g), если lim f/g = 0 (при x -> куда-то).
Очевидно же, что ваше и моё определение O(..) совпадают!
Мне не очевидно.
Тогда вот доказательство эквивалентности по шагам: в одну сторону — %20%3C%20C%20%5Ccdot%20g(x)%20%5Crightarrow%20f(x)%20%5Cleq%20C%20%5Ccdot%20g(x)%5D%20%5Crightarrow%20%5B(%5Cexists%20C%3A%20f(x)%20%3C%20C%20%5Ccdot%20g(x))%20%5Crightarrow%20(%5Cexists%20C%3A%20f(x)%20%5Cleq%20C%20%5Ccdot%20g(x))%5D)
, в обратную — %20%5Cleq%20C%20%5Ccdot%20g(x)%20%5Crightarrow%20f(x)%20%3C%202C%20%5Ccdot%20g(x)%5D%20%5Crightarrow%20%5B(%5Cexists%20C_1%3A%20f(x)%20%5Cleq%20C_1%20%5Ccdot%20g(x))%20%5Crightarrow%20(%5Cexists%20C_2%3D2%20C_1%3A%20f(x)%20%3C%20C_2%20%5Ccdot%20g(x))%5D)
. Как ещё более подробно написать, я не знаю.
f(x)=o(g(x)) по базе B <=> f(x)/g(x) -> 0 по базе B.
Ваше определение эквивалентно моему, когда функции непрерывны, а g не бывает нулем.
И да, о-обозначения бессмысленны без указания базы предела, чего у вас явно не хватает.
И да, о-обозначения бессмысленны без указания базы предела, чего у вас явно не хватает.
Во-первых здесь всё-таки речь о теории сложности, и там обычно используются o, O и т.п. обозначения подразумевая поведение на бесконечности, поэтому (как по мне) можно в таких случаях упускать базу и всем будет понятно. А вообще, я таки указал, что
По поводу равносильности определений — какие именно вы имеете в виду? Если ваше
и моё
, то они не равносильны. Например, sin(n)=O(1) (при n->inf), но по вашему определению это не подходит.
… f(x) < C*g(x) в некоторой области ....
По поводу равносильности определений — какие именно вы имеете в виду? Если ваше
Математическое значение записи «f(x)=O(g(x)) при x->a» представляет собой «существует конечный предел отношения f(x)/g(x) при x->a».
и моё
математическое обозначение f(x)=O(g(x)) обозначает, что f(x) < C*g(x) в некоторой области, где C — некоторая константа
, то они не равносильны. Например, sin(n)=O(1) (при n->inf), но по вашему определению это не подходит.
Последнее задание совсем неочевидно. Для него надо знать, как конкретно выполняется операция s[:len(s)/2] — происходит ли копирование фрагмента строки, или создаётся новая ссылка внутрь содержимого строки s.
Согласен с предыдущими комментариями. Кормен и Конкретная математика — очень хорошие книги, мне нравятся больше Вирта, но он, так сказать, один из столпов.
Вообще для начала хватит одной книги и я из них бы рекомендовал Кормена — хорошо и при этом достаточно доступно объясняет.
Вообще для начала хватит одной книги и я из них бы рекомендовал Кормена — хорошо и при этом достаточно доступно объясняет.
Профит в том, что сразу и наглядно видна общая картина алгоритмов, и это не исключает умение определять сложность на глаз.
Я понимаю что перевод, но достаточно много неточностей/недоговорок. Например со временем вставки — не понятно почему рассматривается только вставка в начало, достаточно редкая операция, обычно или вставка в общем случае или добавление в конец, а у них временная сложность другая.
Плюс — дается понятие Тета-нотации, но нигде в таблицах она не используется. Звездочкой, как я понял — обозначена амортизированная сложность, об этом тоже нигде не сказано. Где-то указано лучшее/среднее/худшее время, а где-то только одно время (надо понимать — среднее, и амортизированное — если со звездочкой).
В табличке по памяти для QuickSort видимо ошибка, т.к. там видимо должно быть log(n), раз даже цвет желтый, ну и там вообще раскраска странная в этом столбце.
С цветовой раскраской по графам в целом не согласен, т.к. это сильно зависит от типа графа, особенно разница между O(|E|) и O(|V|) и между O(|E||V|) и O(|V|^2), O(|E|^2)
Ну и так далее.
Обосную недовольство: в принципе эта табличка приведет только к тому, что заучившие ее люди будут вместо первичного собеседования отсеиваться на последующих. Т.к. заучивание всей таблички никому не нужно. Плюс ко всему важно понимание того, что стоит за сложностью каждого алгоритма, в каких данных этот алгоритм себя показывает хорошо, в каких не очень ит.д. В текущей таблица между деревьями поиска вообще различий не видно.
Видимо все это и есть причина, отвечающая на первый вопрос статьи: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов?».
Плюс — дается понятие Тета-нотации, но нигде в таблицах она не используется. Звездочкой, как я понял — обозначена амортизированная сложность, об этом тоже нигде не сказано. Где-то указано лучшее/среднее/худшее время, а где-то только одно время (надо понимать — среднее, и амортизированное — если со звездочкой).
В табличке по памяти для QuickSort видимо ошибка, т.к. там видимо должно быть log(n), раз даже цвет желтый, ну и там вообще раскраска странная в этом столбце.
С цветовой раскраской по графам в целом не согласен, т.к. это сильно зависит от типа графа, особенно разница между O(|E|) и O(|V|) и между O(|E||V|) и O(|V|^2), O(|E|^2)
Ну и так далее.
Обосную недовольство: в принципе эта табличка приведет только к тому, что заучившие ее люди будут вместо первичного собеседования отсеиваться на последующих. Т.к. заучивание всей таблички никому не нужно. Плюс ко всему важно понимание того, что стоит за сложностью каждого алгоритма, в каких данных этот алгоритм себя показывает хорошо, в каких не очень ит.д. В текущей таблица между деревьями поиска вообще различий не видно.
Видимо все это и есть причина, отвечающая на первый вопрос статьи: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов?».
Обосную недовольство: в принципе эта табличка приведет только к тому, что заучившие ее люди будут вместо первичного собеседования отсеиваться на последующих.
Можно узнать, где это так людей отсеивают, которые на зубок не знают какой алгоритм, какую сложность имеет?
Я как раз говорил об обратном, не нужно знать на зубок какой алгоритм какую сложность имеет. Нужно иметь базовое представление об алгоритмах. Мне сложно представить где на собеседовании могут спросить про кучу фиббоначи. Но вот, например, про quicksort могут, т.к. он очень распространен, а эта табличка дает очень обрезанную и неверную картину касательно этого quicksort (и большинства остального).
А когда человек заучит табличку и будет на зубок знать эту мнимую сложность алгоритмов — как раз это знание на 95% бесполезно. И если в первичном тесте может попасться вопрос «напишите оценки сложности 2-3 известных вам алгоритмов» (обычно речь идет или об очень распространенных алгоритмах или собеседуемому предоставляется возможность самому выбрать алгоритмы для детального разговора), то далее будет детальный разбор тех алгоритмов которые собеседуемый написал — и тут он, заучив только эту табличку, провалится.
А когда человек заучит табличку и будет на зубок знать эту мнимую сложность алгоритмов — как раз это знание на 95% бесполезно. И если в первичном тесте может попасться вопрос «напишите оценки сложности 2-3 известных вам алгоритмов» (обычно речь идет или об очень распространенных алгоритмах или собеседуемому предоставляется возможность самому выбрать алгоритмы для детального разговора), то далее будет детальный разбор тех алгоритмов которые собеседуемый написал — и тут он, заучив только эту табличку, провалится.
А если подойти не со стороны собеседования, а с реальной работы? Допустим, человек ещё не очень свободно ориентируется в множестве существующих алгоритмов. Тогда для конкретной задачи ему было бы неплохо заглянуть в табличку, посмотреть, какой из указанных там алгоритмов даёт лучшие результаты (для конкретных условий), и либо удовлетворённо заметить, что тот алгоритм, о котором он думал изначально, действительно лучше всех, либо разобраться с тем, что предложит табличка. Возможно, ему повезёт, и найдётся действительно подходящий и эффективный алгоритм.
Думаю, что толк от таблички есть. Пойду посмотрю подробнее, что это за фибоначчева куча (на первый взгляд она на меня впечатления не произвела).
Думаю, что толк от таблички есть. Пойду посмотрю подробнее, что это за фибоначчева куча (на первый взгляд она на меня впечатления не произвела).
В худшем случае у Quicksort дополнительная память действительно O(n). Это тот случай, когда тот, кто реализовывал алгоритм, не догадался сравнить длину кусков массива и рекурсивно вызвать сортировку только для короткого куска, а честно написал два рекурсивных вызова.
А вот память в поразрядной сортировке можно ограничить (числом значений разряда)*(количество разрядов): если сортировать начиная со старших разрядов, на каждом шагу сначала посчитать статистику значений каждой цифры, а потом положить каждый объект сразу на место (за O(n)). И рекурсивно вызвать сортировку для следующего разряда.
А вот память в поразрядной сортировке можно ограничить (числом значений разряда)*(количество разрядов): если сортировать начиная со старших разрядов, на каждом шагу сначала посчитать статистику значений каждой цифры, а потом положить каждый объект сразу на место (за O(n)). И рекурсивно вызвать сортировку для следующего разряда.
не понятно почему рассматривается только вставка в начало, достаточно редкая операция, обычно или вставка в общем случае или добавление в конец, а у них временная сложность другая.
Что значит «вставка в общем случае», и почему у неё временная сложность отличается от вставки в начало?
Обычно рассматривают вставку в начало, в конец и в произвольное место. Если мы говорим об амортизированном времени, в списке в начало и в конец — Theta(1), в произвольное место — Theta(n), а для динамического массива в начало и в произвольное место — Theta(n), т.к. нужно сдвигать, а в конец — Theta(1).
С кучами не работаю, но навскидку непонятны первые две строки в таблице с информацией о кучах.
А именно, почему временная сложность в случае отсортированного списка больше чем в случае неотсортированного (увеличить ключ, вставить ключ).
Как может быть отсортированная структура данных «хуже» неотсортированной (знаю что такое иногда бывает, но вряд ли в данном случае)
А именно, почему временная сложность в случае отсортированного списка больше чем в случае неотсортированного (увеличить ключ, вставить ключ).
Как может быть отсортированная структура данных «хуже» неотсортированной (знаю что такое иногда бывает, но вряд ли в данном случае)
Ого! Вот это спасибо! Распечатаю и повешу на стену!
«Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? »
Потому, что толку от такой таблички — ноль.
Потому, что толку от такой таблички — ноль.
А можно для незнающих пояснения к дополнительным данным в сортировках, пожалуйста? Особенно где О(1) получается.
Просто те алгоритмы, где O(1) в этом столбце, используют некоторое константное значение памяти для сортировки, независимо от размера массива (собственно, именно это и написано).
Спасибо, я неправильно понял смысл слов «вспомогательные данные». Подумал, что говорится об ускорении сортировок засчет чего-то заранее известного. Что-то в роде поразрядной сортировки за N, хотя быстрее NlogN изначально невозможно. Сбился, наверное, из-за того, что в предыдущей таблице это еще было подписано памятью.
Например, для сортировки пузырьком вам кроме исходного массива понадобится ещё 3-4 переменные. Их число не зависит от того, массив какого размера сортируется, поэтому дополнительная память, которую они занимают, считается равной O(1). На самом деле это неправда, потому что число битов в представлении индекса растёт как логарифм от длины массива, но все предпочитают работать в модели, где индекс занимает одну ячейку памяти.
В случае быстрой сортировки у нас идут рекурсивные вызовы. В худшем случае, их глубина будет равна двоичному логарифму длины массива, а каждый вызов захватывает на стеке свой набор переменных. Так что общий размер дополнительной памяти — O(log(N)).
Для классической сортировки слиянием нам нужен второй массив, куда мы будем складывать результат слияния отсортированных половинок исходного массива. Можно написать алгоритм так, что дополнительной памяти нужно вдвое меньше, чем размер исходного массива, тем не менее, это O(N). Рекурсия в этом алгоритме не обязательна, но если бы она и была, то много памяти бы не съела.
В случае быстрой сортировки у нас идут рекурсивные вызовы. В худшем случае, их глубина будет равна двоичному логарифму длины массива, а каждый вызов захватывает на стеке свой набор переменных. Так что общий размер дополнительной памяти — O(log(N)).
Для классической сортировки слиянием нам нужен второй массив, куда мы будем складывать результат слияния отсортированных половинок исходного массива. Можно написать алгоритм так, что дополнительной памяти нужно вдвое меньше, чем размер исходного массива, тем не менее, это O(N). Рекурсия в этом алгоритме не обязательна, но если бы она и была, то много памяти бы не съела.
В случае быстрой сортировки у нас идут рекурсивные вызовы. В худшем случае, их глубина будет равна двоичному логарифму длины массива, а каждый вызов захватывает на стеке свой набор переменных. Так что общий размер дополнительной памяти — O(log(N)).
Уверены?
Что можно добиться O(log(N)) — уверен. Следующий уровень рекурсии идёт только для сортировки меньшего из кусков, на которые разделился массив. Его длина меньше половины исходного массива, так что глубина рекурсии не больше O(log(N)). Сортировка оставшегося большего куска организуется с помощью цикла.
Можно ли обойтись без рекурсии и без явно захваченного стека индексов (т.е. используя память O(1)), не уверен. Наверное, можно что-нибудь придумать, но это, скорее всего, будет дольше.
Можно ли обойтись без рекурсии и без явно захваченного стека индексов (т.е. используя память O(1)), не уверен. Наверное, можно что-нибудь придумать, но это, скорее всего, будет дольше.
Да, правильно. а на счет O(1)- ну это уже heapsort получается какой-то. Без кардинальных изменений алгоритма такая магия не сработает.
> Сортировка оставшегося большего куска организуется с помощью цикла.
Можно поподробнее
Можно поподробнее
Если в двух словах:
Здесь split() выполняет один шаг быстрой сортировки и возвращает индекс, на который встал разделяющий элемент.
void qsort(T *arr,int len){
while(len>1){
int medIndex=split(arr,len);
if(2*medIndex>=len){
qsort(arr+(medIndex+1),len-(medIndex+1));
len=medIndex;
}else{
qsort(arr,medIndex);
arr+=(medIndex+1);
len-=(medIndex+1);
}
}
}
Здесь split() выполняет один шаг быстрой сортировки и возвращает индекс, на который встал разделяющий элемент.
Не совсем понятно, для кого и для чего эти таблицы.
Для начинающих программистов, использовать для выбора оптимального алгоритма? Но тогда зачем там например достаточно экзотические Фибоначчиевы пирамиды, и сравнение алгоритмов сортировки (всё равно практически всегда используется функция из библиотеки языка)?
Для изучения теории алгоритмов, асимптотической сложности? Но ведь там куча ошибок и неточностей, даже в определениях всяких о малых и прочих (и в основных таблицах тоже).
Для начинающих программистов, использовать для выбора оптимального алгоритма? Но тогда зачем там например достаточно экзотические Фибоначчиевы пирамиды, и сравнение алгоритмов сортировки (всё равно практически всегда используется функция из библиотеки языка)?
Для изучения теории алгоритмов, асимптотической сложности? Но ведь там куча ошибок и неточностей, даже в определениях всяких о малых и прочих (и в основных таблицах тоже).
Это уже третье определение o-малого, которое я вижу. Обычно под O-большим понимается любая оценка сложности сверху. Например:
2*n^2 = O(n^2)
2*n = O(n^2)
это две корректные O-оценки. Тогда как o-малое — это асимптотически верная оценка сверху. Т.е.:
2*n^2 = o(n^2) < — корректная
2*n = o(n^2) < — некорректная
Аналогично с омегами, но снизу.
Википедия даёт другое определение o-малого. Вы — третье. Перед тем, как использовать o-нотацию в своих публикациях или на собеседованиях, лучше всего сначала уточнить определение, которое будет использоваться.
2*n^2 = O(n^2)
2*n = O(n^2)
это две корректные O-оценки. Тогда как o-малое — это асимптотически верная оценка сверху. Т.е.:
2*n^2 = o(n^2) < — корректная
2*n = o(n^2) < — некорректная
Аналогично с омегами, но снизу.
Википедия даёт другое определение o-малого. Вы — третье. Перед тем, как использовать o-нотацию в своих публикациях или на собеседованиях, лучше всего сначала уточнить определение, которое будет использоваться.
We can draw an analogy between the asymptotic comparison of two functions f and g and the comparison of two real numbers a and b:
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein — Introduction to Algorithms, Third Edition
О нотация с небольшими незначимыми нюансами — одна. И то что вы написали — это что-то странное.
2*n^2 = o(n^2) < — корректнаяЭто с точностью до наоборот, первое — некорректное, второе — корректное.
2*n = o(n^2) < — некорректная
Определения — подгонка некого осязаемого математического смысла в буквы. Их можно написать миллионом способов, и зависеть что-то будет очень мало. У каждого лектора свои формулировки теорем и определений.
bigocheatsheet.com/
*не заметил вовремя, что статья — перевод*
*не заметил вовремя, что статья — перевод*
А я вот не понимаю зачем переводить название алгоритмов и структур. Я не стараюсь сколько-нибудь приубавить ценности стати, но честно не понимаю мотивацию. Меня все эти «сортировка слиянием» (а в Кормене «пирамидальная сортировка») только путают. Давно просто merge не перевожу как «слияние» перевожу как «мержить», поэтому долго сначала не мог понять, что за сортировка такая о которой я ничего не слышал :)
Имел ввиду, что в Кормене есть отличный пример «трудностей перевода» — «пирамидальная сортировка» она же «heap sort». Лучше не переводить такие вещи. ИМХО.
Во так мало-помалу все русские слова выйдут из употребления. Чтобы не иметь трудностей перевода. Вас устроит, если все слова станут не требующими перевода?
На последней диаграмме я вижу 6 графиков, а в легенде 7. Это потому что O(1) и O(log n) сливаются?
У вас рёбра и вершины в первой таблице перепутаны. E — количество рёбер, V — вершин.
Зачем это знать прикладнику, если все алгоритмы написали за него?
видимо чтобы выбирать какой алгоритм взять?
Хотя на мой взгляд от простого знания эффективности алгоритма — в мозгу не прибавится. Вот если знаешь как действительно алгоритм работает, и что в конкретной ситуации можно сделать чтобы его оптимизировать — вот это действительно нужные знания
Хотя на мой взгляд от простого знания эффективности алгоритма — в мозгу не прибавится. Вот если знаешь как действительно алгоритм работает, и что в конкретной ситуации можно сделать чтобы его оптимизировать — вот это действительно нужные знания
Какие «все алгоритмы» написали? Проблем, для которых нет эффективных алгоритмов предостаточно.
Не очень корректные обозначения сложности цветами. Все-таки, О(1) у Фибоначчиевой кучи на всех адекватного размера данных, это далеко не «хорошо».
На самом деле, не все так просто.
В реальной жизни большую роль играет константа перед о-большим.
Поэтому надо различать эффективность алгоритма и его масштабируемость.
В реальной жизни большую роль играет константа перед о-большим.
Поэтому надо различать эффективность алгоритма и его масштабируемость.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Знай сложности алгоритмов