мой вопрос в заголовке. После нескольких часов размышлений и поиска сайтов в Google я пришел к выводу, что не совсем уверен, как решить эту проблему и правильно ли это. Может быть, вы, ребята, могли бы дать мне несколько советов, чтобы решить такие вещи быстрее или проще. Любая помощь приветствуется!
Функция стоимости алгоритма:
T(n) = O(n log n).
Внешний цикл выполняется примерно log(n) раз (поскольку «i» удваивается на каждой итерации), а внутренний цикл выполняется не более n раз на каждой итерации внешнего цикла (на первой итерации внешнего цикла) и не более чем вдвое меньше в каждой последующей итерации внешнего цикла. Вместе это приводит к времени выполнения O (n log n).
public float[] normalize (float[] seq) {
int n = seq.length;
float sum = 0;
int cnt = 0;
int i;
for (i = 1; i < n; i = i + i ) {
for ( int j = 0; j < i; j++) {
sum = sum + seq [j];
}
cnt += i;
}
float[] res = new float [n];
while (i >= 0) {
if (i < n) {
res [i] = seq[i] / (sum / cnt);
}
i--;
}
return res;
}
Функция стоимости алгоритма:
T(n) = O(n log n).
Внешний цикл выполняется примерно log(n) раз (поскольку «i» удваивается на каждой итерации), а внутренний цикл выполняется не более n раз на каждой итерации внешнего цикла (на первой итерации внешнего цикла) и не более чем вдвое меньше в каждой последующей итерации внешнего цикла. Вместе это приводит к времени выполнения O (n log n).
Да, это O(n log n)
.
(int i = 0; i < n; i = i + i)
действительно является логарифмической (n) характеристикой производительности. Не "приблизительно", а именно - приближение заложено в понятие ТТХ.0-i
, где сценарий наихудшего/среднего случая i является постоянной ссылкой из n
, более или менее - таким образом, O(n)
. Объедините два, и у вас есть O(n log n)
.O(n)
, а постоянные множители «не в счёт», так что O(2n * log n)
всё ещё просто упрощено O(n log n)
.Такой анализ, как правило, является единственным способом определить эти вещи. Теоретически вы можете наметить это; в конце концов, эта функция O(n log n)
означает:
Если вы создаете двухмерную линейную диаграмму с «затраченным временем» на оси Y и «значением n» на оси X, и вы на самом деле заполняете значения (сгенерируйте некоторый ввод с n = 1. Запустите его несколько раз и среднее время выполнения. Допустим, это 5 мс. Поставьте «точку» на x = 1, y = 5. Теперь запустите его при n = 2. Допустим, это 7 мс. Поставьте точку на x = 2, y = 7. Оставьте Теперь нарисуйте линию, которая примерно соответствует точкам. ВУАЛА!
O(n log n)
означает: если только вы посмотрите достаточно далеко вправо, с НУЛЕВЫМ указанием того, как далеко вы должны смотреть, кривая будет выглядеть точно так же, как правая часть кривой, описанная математической функцией: y = x * log(x)
, независимо от того, на какой базе этот журнал (все они выглядят одинаково). Речь идет только о том, как это выглядит, следовательно, постоянные факторы не имеют значения, и, следовательно, все, что не «контролирует», можно опустить (например, y=x^2 + x
и y = x^2
выглядят совершенно одинаково, если вы посмотрите достаточно далеко вправо от любой кривой; вот почему O(x^2 + x)
— это просто абракадабра, единственная причина сказать, что это «вот как в конечном итоге выглядит кривая», и эта + x
вещь не имеет отношения к внешнему виду, следовательно, нет смысла включать ее, и, следовательно, O(n)
обозначение никогда не было бы.
В любом случае, это дает вам альтернативный подход: нарисуйте его на графике и сравните, как он выглядит, с несколькими стандартными кривыми. Но я сомневаюсь, что это меньше работы, чем просто рассуждение.
@ user16320675
i = i + i
здесьi
удваивается.