Заказ списка функций с помощью Big O

Question

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

Один из вопросов требует, чтобы мы сравнили ~ 20 функций по значению большой О-О, а затем объединили функции, которые являются большими тетами друг друга. Чтобы упорядочить их, я нарисовал каждый из них от 0 до 100 и сравнил графики, чтобы найти, что лучше других. Это правильный метод сравнения? Если есть более простой способ, что я могу сделать? Как я могу сказать, является ли одна функция большой тета другой функции? Например, небольшая часть списка, который я до сих пор это:

1/n 

2^100 

log(log(n)) 

n^.5 , 3n^.5 

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

2^(log(n)), 5n 

Любое помощь приветствуется .. Я изо всех сил, чтобы обернуть мою голову вокруг Big O, тета и любит.

Answer 1

Эта нотация связана с теорией сложности времени и тем, как размер проблемы (т. Е. Размер пространства «решение») зависит от размера входных параметров.

Ваш вопрос скорее является вопросом математики и более подходит для обмена математикой. Сказав это, this Wikipedia article является хорошей отправной точкой для вас.

Обычно проблемы делятся на (от простейших до самых сложных):

• Постоянного время разрешим - O (1)
времени
• Лога разрешимый - O (журнал (п))
• полиномиального времени решаемый - O (N^2)
• Супер-полиномиальное время разрешимо (более полином)
• Экспоненциального время разрешимо - О (2^поли (п))

Если вы хотите определить, как они ранжированы, выберите набор N = {1 ... n} и подключите каждый элемент этого набора к каждой функции и запишите, как быстро они индивидуально увеличивают размер.