Вопросы с тегом '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