Какова функция стоимости для этого алгоритма?

мой вопрос в заголовке. После нескольких часов размышлений и поиска сайтов в 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).

@ user16320675 i = i + i здесь i удваивается.

Elliott Frisch 03.05.2023 15:36
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
Как вычислять биты и понимать побитовые операторы в Java - объяснение с примерами
В компьютерном программировании биты играют важнейшую роль в представлении и манипулировании данными на двоичном уровне. Побитовые операции...
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Поднятие тревоги для долго выполняющихся методов в Spring Boot
Приходилось ли вам сталкиваться с требованиями, в которых вас могли попросить поднять тревогу или выдать ошибку, когда метод Java занимает больше...
Полный курс Java для разработчиков веб-сайтов и приложений
Полный курс Java для разработчиков веб-сайтов и приложений
Получите сертификат Java Web и Application Developer, используя наш курс.
0
1
56
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Да, это O(n log n).

  1. for (int i = 0; i < n; i = i + i) действительно является логарифмической (n) характеристикой производительности. Не "приблизительно", а именно - приближение заложено в понятие ТТХ.
  2. Затем для каждого из них вы перебираете 0-i, где сценарий наихудшего/среднего случая i является постоянной ссылкой из n, более или менее - таким образом, O(n). Объедините два, и у вас есть O(n log n).
  3. Остальное 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) обозначение никогда не было бы.

В любом случае, это дает вам альтернативный подход: нарисуйте его на графике и сравните, как он выглядит, с несколькими стандартными кривыми. Но я сомневаюсь, что это меньше работы, чем просто рассуждение.

Другие вопросы по теме

Есть ли простой способ построить эффективную границу с помощью R?
Как сделать вложенный цикл for в R более эффективным для записи вывода в фрейм данных?
Как повысить производительность при случайном выборе кластеров и добавлении наблюдений?
Как я могу сгенерировать простые палиндромы в заданном диапазоне без полного поиска и использования функции проверки?
Как я могу сделать свою рекурсивную программу для вывода факториала числа более эффективной?
Есть ли способ оптимизировать скорость изменения значений в фрейме данных с> 2 миллионами строк?
Лучший способ создать цикл для умножения матрицы на каждый из ее элементов, а затем суммирования результатов
Как я могу написать этот рабочий код для повышения производительности?
Excel VBA эффективно обновляет даты с помощью неуникальных строковых значений и логических данных
Применение «функций кластеризации» к ряду линейных моделей