У меня есть понимание о нотации Big-Oh. Но как мне интерпретировать, что означает O(O(f(n)))? Означает ли это скорость роста скорости роста?
Что означает O(O(f(n)))?
Ответы (2)
x = O(n) в основном означает x <= kn для некоторой константы k.
Таким образом, x = O((O(n)) означает x <= pO(n) для некоторой константы p, что означает x <= pqn для некоторой константы q.
Пусть k = pq.
Затем x = O((O(n)) = O(n).
Другими словами, O(O(f(n))) = O(f(n)).
Мне любопытно, где вы видели, чтобы такое обозначение использовалось?
person
wookie919
schedule
14.09.2014
Это одно из заданий университетской программы.
- person jagvirsingh5; 15.09.2014
С точки зрения Big-Oh:
g(n) = O(f(n)) означает g(n) <= K*f(n) для некоторого K (и после некоторого n1)
Но тогда h(n) = O(O(f(n)) будет означать что-то вроде h(n) <= L * M * f(n) для некоторых Л, М, после некоторых n > n1, n2.
person
Pieter21
schedule
14.09.2014
Что, в свою очередь, означает просто O(f(n))
- person soulcheck; 15.09.2014
Где, черт возьми, ты учишься этому материалу? Я нахожу это несколько чуждым, но увлекательным.
- person jay_t55; 15.09.2014
Университетские штучки... Либо математика, либо информатика.
- person Pieter21; 15.09.2014
O— это функция, которая принимает функцию в качестве аргумента, и чтоOиfимеют общую сигнатуру. - person AlexanderBrevig schedule 15.09.2014