Алгоритм с временной сложностью O (log N^3/M)

Question

Я пытаюсь написать алгоритм с временной сложностью O (log N^3/M). Однако я не уверен в части журнала N/M. Я был бы признателен, если бы кто-нибудь мог подтвердить, правильно ли мой алгоритм.

for (int i = 1; i < N; i = i*2) // log N 
    for (int i = 1; i < N; i = i*2) // log N 
    *for (int i = 1; i < N; i += M+i*2) // log N/M 

* Если for (int i = 1; i < N; i += M) имеет O (N/M) временную сложность, и О (журнал N) требует i следует умножить на константу, то можно сделать вывод, что О (Log N/M) может быть достигнуто, если мы добавляем константу в i и умножаем ее на другую константу одновременно.

Каким будет алгоритм для временной сложности O (N/log N)?

Answer 1

Я думаю, что: for (int i = 1; i < N; i += M+i*2) не O (журнал (N/M)) потому, что позволяет говорить о том, что цикл будет выполняться в к раз, то мы имеем: к * М + 2^к> = N -> что не приводит к k = O (log (N/M)).

Вместо этого вы могли бы написать:

for (int i = 1; i < N/M; i =i*2) 

это, очевидно, O (журнал (N/M)).