Ответ 1

В общем, нет способа определить сложность данной функции

Внимание! Стена ввода текста!

1. Есть очень простые алгоритмы, которые никто не знает, останавливаются они или нет.

Существует нет алгоритма, который может решить, останавливается ли данная программа или нет, если задан определенный ввод. Вычисление вычислительной сложности - еще более сложная проблема, так как нам нужно не только доказать, что алгоритм останавливается, но и нужно доказать, насколько быстро он это делает.

//The Collatz conjecture states that the sequence generated by the following
// algorithm always reaches 1, for any initial positive integer. It has been
// an open problem for 70+ years now.
function col(n){
    if (n == 1){
        return 0;
    }else if (n % 2 == 0){ //even
        return 1 + col(n/2);
    }else{ //odd
        return 1 + col(3*n + 1);
    }
}

2. Некоторые алгоритмы имеют странные и невыполненные сложности

Общая "схема определения сложности" будет легко усложняться из-за этих парней

//The Ackermann function. One of the first examples of a non-primitive-recursive algorithm.
function ack(m, n){
    if(m == 0){
        return n + 1;
    }else if( n == 0 ){
        return ack(m-1, 1);
    }else{
        return ack(m-1, ack(m, n-1));
    }
}

function f(n){ return ack(n, n); }

//f(1) = 3
//f(2) = 7
//f(3) = 61
//f(4) takes longer then your wildest dreams to terminate.

3. Некоторые функции очень просты, но будут путать много видов попыток статического анализа

//Mc'Carthy 91 function. Try guessing what it does without
// running it or reading the Wikipedia page ;)
function f91(n){
    if(n > 100){
        return n - 10;
    }else{
        return f91(f91(n + 11));
    }
}

Тем не менее, нам все еще нужен способ найти сложность вещей, верно? Для петель - простой и общий шаблон. Возьмите первый пример:

for(i=0; i<N; i++){
   for(j=0; j<i; j++){
       print something
   }
}

Поскольку каждый print something равен O (1), временная сложность алгоритма будет определяться тем, сколько раз мы запускаем эту строку. Хорошо, как упоминалось в вашей ТП, мы делаем это, рассматривая комбинации в этом случае. Внутренний цикл будет работать (N + (N-1) +... + 1) раз, в общей сложности (N + 1) * N/2.

Поскольку мы пренебрегаем константами, получаем O (N ²).

Теперь для более сложных случаев мы можем получить более математическое. Попробуйте создать функцию, значение которой представляет собой продолжительность выполнения алгоритма, учитывая размер N ввода. Часто мы можем построить рекурсивную версию этой функции непосредственно из самого алгоритма, и поэтому вычисление сложности становится проблемой размещения границ этой функции. Мы называем эту функцию a recurrence

Например:

function fib_like(n){
    if(n <= 1){
        return 17;
    }else{
        return 42 + fib_like(n-1) + fib_like(n-2);
    }
 }

легко видеть, что время работы в терминах N будет задаваться выражением

T(N) = 1 if (N <= 1)
T(N) = T(N-1) + T(N-2) otherwise

Ну, T (N) - это только доброжелательная функция Фибоначчи. Мы можем использовать индукцию, чтобы наложить на нее некоторые оценки.

Для примера, Докажем, по индукции, что T (N) <= 2 ^ n для всех N (т.е. T (N) есть O (2 ^ n))/p >

• базовый регистр: n = 0 или n = 1

    T(0) = 1 <= 1 = 2^0
    T(1) = 1 <= 2 = 2^1

• индуктивный случай (n > 1):

    T(N) = T(n-1) + T(n-2)
    aplying the inductive hypothesis in T(n-1) and T(n-2)...
    T(N) <= 2^(n-1) + 2^(n-2)
    so..
    T(N) <= 2^(n-1) + 2^(n-1)
         <= 2^n

(мы можем попытаться сделать что-то подобное, чтобы доказать нижнюю границу)

В большинстве случаев, имея хорошее предположение о конечном времени выполнения функции, вы сможете легко решить проблемы повторения с индуктивным доказательством. Конечно, это требует, чтобы вы могли угадать сначала - здесь может помочь только много практики.

И как последнее замечание, я хотел бы указать на Мастер-теорему, единственное правило для более сложных проблем повторения Теперь я могу подумать, что это обычно используется. Используйте его, когда вам приходится иметь дело с алгоритмом сложного деления и покорения.

Кроме того, в вашем примере "if case" я решил бы это, обманывая и разбивая его на две отдельные петли, которые на; t есть, если внутри.

for (int i = 0; i < n; i++) {
    if (i % 2 ==0) {
        for (int j = i; j < n; j++) { ... }
    } else {
        for (int j = 0; j < i; j++) { ... }
    }
}

Имеет ту же среду выполнения, что и

for (int i = 0; i < n; i += 2) {
    for (int j = i; j < n; j++) { ... }
}

for (int i = 1; i < n; i+=2) {
    for (int j = 0; j < i; j++) { ... }
}

И каждая из двух частей легко может быть обозначена как O (N ^ 2) для общего числа, которое также равно O (N ^ 2).

Обратите внимание, что я использовал хороший трюк, чтобы избавиться от "if" здесь. Нет общего правила для этого, как показано в примере алгоритма Collatz

Ответ 2

В общем, решающая сложность алгоритма теоретически невозможна.

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

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println("*");
    }
}

Теперь мы хотим проанализировать его сложность, поэтому добавим простой счетчик, который подсчитывает количество исполнений внутренней строки:

int counter = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println("*");
        counter++;
    }
}

Поскольку строка System.out.println не имеет значения, удалите ее:

int counter = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        counter++;
    }
}

Теперь, когда у нас остался только счетчик, мы можем, очевидно, упростить внутренний цикл:

int counter = 0;
for (int i = 0; i < n; i++) {
    counter += n;
}

... потому что мы знаем, что приращение выполняется ровно n раз. И теперь мы видим, что счетчик увеличивается на n ровно n раз, поэтому мы упрощаем это:

int counter = 0;
counter += n * n;

И мы вышли с (правильной) сложностью O (n ²):) Это там в коде:)

Посмотрим, как это работает для рекурсивного калькулятора Фибоначчи:

int fib(int n) {
  if (n < 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

Измените процедуру так, чтобы она возвращала количество итераций, проведенных внутри нее, вместо фактических чисел Фибоначчи:

int fib_count(int n) {
  if (n < 2) return 1;
  return fib_count(n - 1) + fib_count(n - 2);
}

Это еще Фибоначчи!:) Итак, теперь мы знаем, что рекурсивный вычислитель Фибоначчи имеет сложность O (F (n)), где F - само число Фибоначчи.

Хорошо, посмотрим на что-то более интересное, скажем, простую (и неэффективную) mergesort:

void mergesort(Array a, int from, int to) {
  if (from >= to - 1) return;
  int m = (from + to) / 2;
  /* Recursively sort halves */
  mergesort(a, from, m);
  mergesort(m, m,    to);
  /* Then merge */
  Array b = new Array(to - from);
  int i = from;
  int j = m;
  int ptr = 0;
  while (i < m || j < to) {
    if (i == m || a[j] < a[i]) {
      b[ptr] = a[j++];
    } else {
      b[ptr] = a[i++];
    }
    ptr++;
  }
  for (i = from; i < to; i++)
    a[i] = b[i - from];
}

Поскольку нас не интересует фактический результат, но сложность, мы меняем процедуру так, чтобы она фактически возвращала количество выполняемых единиц работы:

int mergesort(Array a, int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  /* Recursively sort halves */
  int count = 0;
  count += mergesort(a, from, m);
  count += mergesort(m, m,    to);
  /* Then merge */
  Array b = new Array(to - from);
  int i = from;
  int j = m;
  int ptr = 0;
  while (i < m || j < to) {
    if (i == m || a[j] < a[i]) {
      b[ptr] = a[j++];
    } else {
      b[ptr] = a[i++];
    }
    ptr++;
    count++;
  }
  for (i = from; i < to; i++) {
    count++;
    a[i] = b[i - from];
  }
  return count;
}

Затем мы удаляем те строки, которые фактически не влияют на подсчеты и упрощают:

int mergesort(Array a, int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  /* Recursively sort halves */
  int count = 0;
  count += mergesort(a, from, m);
  count += mergesort(m, m,    to);
  /* Then merge */
  count += to - from;
  /* Copy the array */
  count += to - from;
  return count;
}

Еще немного упростить:

int mergesort(Array a, int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  int count = 0;
  count += mergesort(a, from, m);
  count += mergesort(m, m,    to);
  count += (to - from) * 2;
  return count;
}

Теперь мы можем фактически отказаться от массива:

int mergesort(int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  int count = 0;
  count += mergesort(from, m);
  count += mergesort(m,    to);
  count += (to - from) * 2;
  return count;
}

Теперь мы можем видеть, что на самом деле абсолютные значения от и не имеют значения, но только их расстояние, поэтому мы модифицируем это:

int mergesort(int d) {
  if (d <= 1) return 1;
  int count = 0;
  count += mergesort(d / 2);
  count += mergesort(d / 2);
  count += d * 2;
  return count;
}

И затем мы получаем:

int mergesort(int d) {
  if (d <= 1) return 1;
  return 2 * mergesort(d / 2) + d * 2;
}

Здесь очевидно, что d для первого вызова - это размер массива, который нужно отсортировать, поэтому у вас есть повторяемость для сложности M (x) (это видно на второй строке:)

M(x) = 2(M(x/2) + x)

и вам нужно решить, чтобы перейти к решению закрытой формы. Это проще всего, если угадать решение M (x) = x log x и проверить для правой части:

2 (x/2 log x/2 + x)
        = x log x/2 + 2x
        = x (log x - log 2 + 2)
        = x (log x - C)

и проверить, что она асимптотически эквивалентна левой стороне:

x log x - Cx
------------ = 1 - [Cx / (x log x)] = 1 - [C / log x] --> 1 - 0 = 1.
x log x

Ответ 3

Несмотря на то, что это более обобщение, мне нравится думать о Big-O в терминах списков, где длина списка - N элементов.

Таким образом, если у вас есть цикл for, который выполняет итерацию по всему списку, это O (N). В вашем коде у вас есть одна строка, которая (по отдельности сама по себе) равна 0 (N).

for (int i = 0; i < n; i++) {

Если у вас есть цикл for, вложенный внутри другого цикла for, и вы выполняете операцию над каждым элементом в списке, который требует, чтобы вы просмотрели каждый элемент в списке, то вы выполняете операцию N раз для каждого из N таким образом, O (N ^ 2). В приведенном выше примере вы делаете на самом деле другой цикл, вложенный внутри цикла for. Поэтому вы можете думать об этом так, как если бы каждый цикл был равен 0 (N), а затем, поскольку они вложены, умножьте их на общее значение 0 (N ^ 2).

И наоборот, если вы просто выполняете быструю операцию над одним элементом, то это будет O (1). Существует не "список длины n", а только однократная однократная операция. Чтобы привести это в контексте, в приведенном выше примере, выполните операцию:

if (i % 2 ==0)

равно 0 (1). Важно не "if", а тот факт, что проверка того, что один элемент равен другому элементу, - это быстрая операция для одного элемента. Как и раньше, оператор if вложен в ваш внешний цикл. Однако, поскольку он равен 0 (1), вы умножаете все на "1", и поэтому нет никакого "заметного" влияния в конечном счете для времени выполнения всей функции.

Для журналов и для более сложных ситуаций (например, эта операция подсчета до j или i, а не только n снова), я бы указал вам на более элегантное объяснение .

Ответ 4

Мне нравится использовать две вещи для нотации Big-O: стандартный Big-O, который является наихудшим сценарием, и средний Big-O, что обычно заканчивается. Это также помогает мне помнить, что нота Big-O пытается аппроксимировать время выполнения как функцию N, количество входов.

TA объяснил это чем-то вроде комбинаций. Например, n выбирает 2 = (n (n-1))/2 = n ^ 2 + 0,5, а затем удаляет константу так, чтобы она становилась n ^ 2. Я могу поместить int test values ​​и попробовать, но как эта комбинация входит?

Как я уже сказал, нормальный большой-O - худший сценарий. Вы можете попытаться подсчитать количество раз, когда каждая строка будет выполнена, но проще просто взглянуть на первый пример и сказать, что есть две петли по длине n, одна встроенная в другую, так что это n * п. Если бы они были один за другим, это было бы n + n, равное 2n. Поскольку это приближение, вы просто говорите n или linear.

Что делать, если инструкция ifres? Как определяется сложность?

Это то, где для меня средний случай и лучший случай помогают много для организации моих мыслей. В худшем случае вы игнорируете if и say n ^ 2. В среднем случае для вашего примера у вас есть цикл над n, с другим циклом над частью n, который происходит половину времени. Это дает вам n * n/x/2 (x - любая доля n зацикливается в ваших встроенных циклах. Это дает вам n ^ 2/(2x), так что вы получите n ^ 2 точно так же. потому что его приближение.

Я знаю, что это не полный ответ на ваш вопрос, но, надеюсь, он проливает некоторый свет на аппроксимацию сложностей в коде.

Как было сказано в ответах выше моего, явно невозможно определить это для всех фрагментов кода; Я просто хотел добавить идею использования среднего случая Big-O для обсуждения.

Ответ 5

Для первого фрагмента это просто n ^ 2, потому что вы выполняете n операций n раз. Если j был инициализирован до i или поднялся до i, объяснение, которое вы опубликовали, было бы более уместным, но, поскольку оно стоит, это не так.

Во втором фрагменте вы можете легко увидеть, что половина времени будет выполнена первой, а вторая будет выполнена в другую половину времени. В зависимости от того, что там (надеюсь, оно зависит от n), вы можете переписать уравнение как рекурсивное.

Рекурсивные уравнения (включая третий фрагмент) могут быть записаны как таковые: третий будет выглядеть как

T(n) = T(n-1) + 1

Мы можем легко видеть, что O (n).

Ответ 6

Big-O - просто приближение, он не говорит, сколько времени выполняется алгоритм для выполнения, он просто говорит о том, сколько времени потребуется, когда размер его ввода растет.

Итак, если входной размер N и алгоритм оценивает выражение постоянной сложности: O (1) N раз, сложность алгоритма линейна: O (N). Если выражение имеет линейную сложность, алгоритм имеет квадратичную сложность: O (N * N).

Некоторые выражения имеют экспоненциальную сложность: O (N ^ N) или логарифмическую сложность: O (log N). Для алгоритма с циклами и рекурсией умножьте сложности каждого уровня цикла и/или рекурсии. С точки зрения сложности, цикл и рекурсия эквивалентны. Алгоритм, который имеет разные сложности на разных этапах алгоритма, выбирает наивысшую сложность и игнорирует остальные. И, наконец, все постоянные сложности считаются эквивалентными: O (5) совпадает с O (1), O (5 * N) совпадает с O (N).