Большой-O, когда значение n становится очень маленьким?
Если я понимаю, что вы ищете: найдите (значение индекса, расположение столбца) значения в кадре данных. Вы можете использовать понимание списка в цикле. Вероятно, не будет самым быстрым, если ваш фрейм данных большой.
# assume this dataframe
df = pd.DataFrame({'col':['abc', 'def','wert','abc'], 'col2':['asdf', 'abc', 'sdfg', 'def']})
# list comprehension
[(df[col][df[col].eq('abc')].index[i], df.columns.get_loc(col)) for col in df.columns for i in range(len(df[col][df[col].eq('abc')].index))]
# [(0, 0), (3, 0), (1, 1)]
измените df.columns.get_loc на col, если хотите указать значение столбца, а не местоположение:
[(df[col][df[col].eq('abc')].index[i], col) for col in df.columns for i in range(len(df[col][df[col].eq('abc')].index))]
# [(0, 'col'), (3, 'col'), (1, 'col2')]
7 ответов
Big O doesn't describe the execution time of a function, just the growth. All functions have some constant factor or overhead that needs to be added in. When n is low, this overhead can greatly dwarf any improvements to the algorithm - an algorithm that requires 50ms per operation but has O(n) will perform worse for small n than an algorithm that requires 5 ms per operation, but has O(n*n).
This is why, in general, for small sets big O doesn't matter. For most objects with simple comparisons, a quick sort on 10 items will not be noticiably faster than a bubble sort, a linear search on 100 items will probably be faster than a binary tree, and so on.
The course material gets harder to understand as the number of lectures attended (N) becomes very small.
Возможно, следующее является примером «O (n) отклонения от функции, когда n становится очень маленьким»:
Рассмотрим операцию, которая требует, например, времени «50 раз n , плюс n в квадрате ».
Когда n велико, то преобладает член« n в квадрате », и поэтому можно сказать, что операция будет« O (n в квадрате) ».
Однако, когда n мало, член "n в квадрате" будет незначительным, а член "50 умножить на n" будет доминировать, и поэтому, когда (и только когда) n мало, можно сказать, что оно равно O (n).
В основе нотации Big-O лежит асимптотическая производительность алгоритма. По мере увеличения N член в нотации Big-O начинает доминировать над общим временем. Например, в алгоритме O (N ^ 2) общее время T (N) может быть:
T(N) = a * N * N + b * N + c
По мере того, как N становится все больше и больше, член в N ^ 2 доминирует, независимо от значения b или c .
Однако, когда N мало, значения b и c имеют значение.
Например, если a = 0,001, b = 1000 и c = 1 000 000.
N ~ T(N) [1 significant figure]
1 1,000,000 (almost all c)
1,000 2,000,000 (50:50 split on b and c)
1,000,000 2,000,000,000 (50:50 split on a and b)
1,000,000,000 1,000,000,000,000,000 (almost all a)
Итак, если вы проигнорировали младший порядок термины, производительность при низком N будет полностью искажена. При высоком N члены младшего порядка не имеют значения.
Большой не по теме, но для полноты я хочу упомянуть некоторые другие нотации, которые связаны с нотацией Big_o и обычно используются в теоретической информатике и которые вы можете найти в компьютерах. научная литература: нотация Big-Θ, нотация Big-Ω и нотация small-o. Это просто другие (и более точные) описания темпов роста. Обозначение маленького o легко ошибочно принимают за обозначение большого o.
Маленькое-o также является отношением между двумя функциями f (x) и g (x). Утверждение, что «f (x) мало от g (x)», означает, что f (x) растет намного быстрее, чем g (x). В более математических терминах говорится, что предел f (x) / g (x) равен нулю, поскольку x стремится к бесконечности.
Как упоминалось в предыдущих ответах, нотация большого О используется для описания верхней границы скорости роста алгоритма. На самом деле это отношение между двумя функциями f (x) и g (x), где f (x) = O (g (x)), когда x стремится к бесконечности.
См. страницу википедии Big-o для красивого и лаконичного представления различных обозначений.
Чтобы расширить ответ выше, обозначение Big-Oh измеряет возможный рост функции или ее ограничивающее поведение.
f = O (g) тогда и только тогда, когда существуют N и константа c (которая может быть функцией
of N) такое, что для всех n> N,
f (n) <= c * g (n)
Допустим, f = 10000000 * n и g = n ^ 2.
f = O (g), однако, если вы посмотрите на слишком маленькие значения n, скажем менее 10000000 и положим c = 1, вы увидите, что g (n) <= f (n).
Чтобы добавить более экстремальный пример, вы бы предпочли иметь дело с алгоритмом с сложность n ^ 100000 или алгоритм со сложностью 2 ^ (. 0000000001n). Для разумные размеры задач, последнее лучше. Что делает CS настолько прекрасен, что допускает такие злоупотребления, однако наиболее естественным алгоритмы этим не пользуются. Большинство алгоритмов полиномиального времени имеют небольшие константы (по крайней мере, после небольшой работы).
Удачи!
Согласно определению:
f (n) = Θ (g (n)) означает набор из всех функций f (n) , таких, что должны быть константы c1 и c2 и также n0 , где все эти случаи истинны :
- c1. g (n) - неотрицательный член или 0.
- c1. g (n) <= f (n) [g (n) должен быть нижней границей для определенного n]
- f (n) <= c2. g (n) [g (n) также должна быть верхней границей, поскольку мы определяем Θ].
- для всех n больше, чем выбранный n0
Итак, все, что нам нужно сделать, это выберите такие c1, c2 и n0, которые делают ВСЕ условия истинными. Поэтому для определенных комбинаций c1 c2, если вы выбираете n