Вообще говоря, всегда верно?Big-O of log против квадратного корня
log (n) = O (n a/(a + 1))? S.T. a - любое постоянное положительное целое число, возможно, очень большое.
Если нет, то какое наибольшее значение имеет значение a, для которого это утверждение будет иметь силу?
В функции идут, журнал (п) всегда растет медленнее, чем плюбой мощности при п становится большим. См. https://math.stackexchange.com/questions/1663818/does-the-logarithm-function-grow-slower-than-any-polynomial для доказательства.
Так что, пока является постоянным положительным целым числом, это действительно не имеет значения, что его значение, как это всегда можно будет найти константы C и к таким образом, что журнал (п) < = | C (п/( +) | + к, который является определение большого-O
Однако, вы можете понять это интуитивно.: п/( +) подходы п как a будет большой. Естественно, журнал (n) всегда O (n).
Если вы имеете в виду log(n)∈O(n^(a/(a+1)), да это верно для всех Позитив Целые для а, потому что a/a+1 < 1 => n^(a/(a+1) ∈ O(n) и из-за log(n) ∈ O(n) => log(n) ∈ O(n^(a/(a+1))
Основным фактом является то, что из-за вогнутости логарифм, всегда ниже касательной. Так
log(x) <= log(e) + 1/e * (x-e) = x/e
Таким образом
log(n) = O(n).
Теперь нужно только применять законы логарифм найти
log(n) = 1/c * log(n^c) <= 1/(ce) * n^c
и, таким образом, log(n)=O(n^c) для любого положительного C.
* «Это действительно не имеет значения, что такое значение a» *: это имеет значение немного: будет ли оно удерживаться, когда * a * находится в интервале [-1, 0]? – trincot
Вы неправильно поняли. Он спрашивает о сложности журнала функций (N), когда N становится сколь угодно большим. –
@ trincot, OP указывает, что a является «любым постоянным положительным целым числом». a не может находиться в интервале [-1, 0]. – pymaxion