Вопросы с тегом 'time-complexity'

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

Что такое простое английское объяснение "Big O"?

Я предпочел бы как можно меньше формального определения и простую математику.
28 янв. '09 в 11:10
47

Как проверить, содержит ли массив значение в JavaScript?

Какой самый краткий и эффективный способ выяснить, содержит ли массив JavaScript значение? Это единственный способ сделать это: function contains(a, obj) { for (var i = 0; i < a.length; i++) { if (a[i] === obj) { return t...
25 окт. '08 в 22:14
32

Что означает O (log n)?

Я узнаю о времени работы Big O Notation и времени амортизации. Я понимаю понятие O (n) линейного времени, означающего, что размер входных данных влияет на рост алгоритма пропорционально... и то же самое относится, например, к квадратичному времени O...
21 февр. '10 в 20:05
26

Как вы можете профилировать скрипт Python?

Project Euler и другие соревнования по кодированию часто имеют максимальное время для запуска, или люди хвастаются тем, как быстро выполняется их конкретное решение. С python иногда подходы несколько kludgey - то есть добавление кода времени в __mai...
24 февр. '09 в 16:01
10

Как найти временную сложность алгоритма

Вопрос Как найти временную сложность алгоритма? Что я сделал до публикации вопроса о SO? Я прошел этот, этот и многие другие ссылки Но нет, где я смог найти ясное и прямое объяснение того, как рассчитать сложность времени. Что я знаю? Ска...
14 июн. '12 в 11:21
5

Если строки .NET неизменны в .NET, то почему Подстановка принимает O (n) время?

Учитывая, что строки являются неизменными в .NET, мне интересно, почему они были сконструированы таким образом, что string.Substring() занимает время O (substring.Length), а не O(1)? то есть. какие были компромиссы, если они есть?
19 июл. '11 в 6:05
9

В чем разница между Θ (n) и O (n)?

Иногда я вижу Θ (n) со странным символом Θ с чем-то посреди него, а иногда просто O (n). Это просто лень печатать, потому что никто не знает, как набирать этот символ, или это означает что-то другое?
22 янв. '09 в 22:58
12

Вычислительная сложность последовательности Фибоначчи

Я понимаю запись Big-O, но я не знаю, как вычислить ее для многих функций. В частности, я пытался выяснить вычислительную сложность наивной версии последовательности Фибоначчи: int Fibonacci(int n) { if (n <= 1) return n; else ...
11 дек. '08 в 20:20
22

Существуют ли случаи, когда вы предпочитаете более высокий алгоритм сложной сложности по сравнению с более низким?

Существуют ли случаи, когда вы предпочитаете O(log n) сложность по времени для O(1) временной сложности? Или O(n) до O(log n)? Есть ли у вас примеры?
09 дек. '15 в 13:25
3

Разница между примечаниями Big-O и Little-O

В чем разница между нотами Big-O O(n) и Маленькая-O нотация O(n)?
01 сент. '09 в 20:22
5

Являются ли 2 ^ n и n * 2 ^ n одинаковой временной сложностью?

Ресурсы, которые я обнаружил по временной сложности, неясно, когда можно игнорировать термины в уравнении сложности времени, в частности, с не-полиномиальными примерами. Мне ясно, что, учитывая что-то вида n 2 + n + 1, последние два члена несущест...
13 февр. '14 в 20:32
13

как рассчитать сложность двоичного поиска

Я слышал, как кто-то сказал, что, поскольку двоичный поиск уменьшает вход, необходимый для поиска, это алгоритм log (n). Поскольку я не из математического фона, я не могу к нему относиться. Может кто-нибудь объяснить это немного подробнее? нужно ли ч...
18 нояб. '11 в 15:50
15

Является ли хэш-карта Java действительно O (1)?

Я видел несколько интересных заявлений о SOh-хеш-картах SO и их времени поиска O(1). Может кто-нибудь объяснить, почему это так? Если эти хэш-карты не сильно отличаются от любых алгоритмов хеширования, которые я купил, всегда должен существовать наб...
28 июн. '09 в 16:49
16

Максимальная прибыль от одной продажи

Предположим, нам задан массив из n целых чисел, представляющих цены на акции за один день. Мы хотим найти пару (buyDay, sellDay) с buyDay & le; sellDay, так что, если бы мы купили акции на buyDay и продали их на sellDay, мы бы максимизировали наш...
16 авг. '11 в 23:45
12

Сортировка в области компьютерных наук и сортировка в "реальном" мире

Я думал о сортировке алгоритмов в программном обеспечении и возможных способах преодоления препятствия O(nlogn). Я не думаю, что это можно отсортировать быстрее в практическом смысле, поэтому, пожалуйста, не думайте, что я это делаю. С учетом сказа...
11 янв. '17 в 6:58