Любая функция, чье время выполнения имеет вид (log n) k - это O ((log n) k ). Это выражение не сводится к любой другой примитивной функции, использующей простые преобразования, и довольно часто можно увидеть алгоритмы с такими средами исполнения, как O (n (log n) 2 ). Функции с такой скоростью роста называются полилогарифмическими.
Кстати, обычно (log n) k записывается как log k n, поэтому приведенный выше алгоритм будет иметь время выполнения O (n log 2 п. В вашем случае функция log 2 n + log n будет иметь значение O (log 2 n).
Однако любая функция со временем выполнения журнала формы (n k ) имеет время выполнения O (log n), предполагая, что k является константой. Это связано с тем, что log (n k ) = k log n с использованием тождеств логарифма, а k log n равно O (log n), поскольку k является константой. Вы должны быть осторожны, чтобы не делать слепой вывод, что алгоритм, который является O (log (n k )), тем не менее, является O (log n); если k является параметром функции или зависит от n, правильное вычисление big-O в этом случае будет O (k log n).
В зависимости от контекста, в котором вы работаете, иногда вы видите обозначение Õ (f (n)), означающее O (f (n) log k n) для некоторой константы k. Это иногда называется « soft-O » и используется в тех случаях, когда логарифмические термины не имеют значения. В этом случае вы могли бы сказать, что обе функции Õ (1), хотя это использование не распространено в простом алгоритмическом анализе (фактически, за пределами Википедии, я видел, что это использовалось только один раз).
Надеюсь, это поможет!