Ответ 1

Нет, это еще O (n ^ 2). Вы только немного улучшили константу. Вам все еще нужно сделать две петли - в основном наивный подсчет, когда петель измеряет большое время O, должен сказать вам это.

Кроме того, нет такой вещи, как O (n + 1/2n). Обозначение Big O - дать вам представление о том, какой порядок следует предпринять. n + 1/2n = 1,5n. Так как большой O сбрасывает все постоянные факторы, это будет просто n.

Вы можете победить O (n ^ 2) без дополнительной памяти. Если вы не можете сортировать строки по значению ascii (nlog (n)), а затем пройдите по массиву, ищущему обман (n время) для O (n + nlogn) = O (nlogn) time. Там, вероятно, другие трюки.

Обратите внимание, что метод сортировки может не дать лучшего времени исполнения, но наивный способ имеет наилучшее время выполнения 1, в то время как сортировка первого алгоритма должна сортироваться, поэтому он имеет лучший случай nlogn. Таким образом, лучшее время для большого времени не может быть лучшим выбором.

Ответ 2

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

Сначала сделайте strnlen(str, 256). Если вы получите больше 255, return 0. По принципу голубины какой-то характер должен происходить более одного раза. Эта операция принимает только O(1), так как мы рассматриваем только ограниченный префикс строки.

Теперь строка короче константы (256), поэтому используйте любой наивный алгоритм для завершения только O(1) дополнительного времени.

Ответ 3

Короткий ответ

Если количество возможных символов (не путать с длиной строк) не фиксировано (не здесь), сложность времени вашего алгоритма O (n ^ 2). Если мы сделаем предположение, существует только фиксированное число допустимых символов (в данном случае 255/4G), ваш алгоритм работает в худшем случае O (n). Если условие выполнено, тогда алгоритм может быть легко улучшен для работы в O (1).

Замечание об асимптотическом поведении и большом-ох: это теоретические результаты. Это не потому, что алгоритм работает в O (1), он работает в разумные сроки. Это означает, что он работает в постоянное время. Таким образом, асимптотически говоря, не будет иметь значения, вводите ли вы строку длиной 10 ¹⁰⁰⁰ или одну с длиной 10 ^10'000 (если эти длины являются большими достаточно). Время, которое требуется, может быть более чем в сто раз больше, чем возраст Вселенной.

Объяснение

Вы можете сделать простой анализ более чем наихудшего для циклов for:

for (; *scout != '\0'; ++scout, ++offset)
    for (start = (char *)str + offset; *start != '\0'; ++start)
        //single statement

Теперь мы хотим узнать, сколько раз будет повторяться один оператор (содержащий фиксированное количество операторов). Поскольку вы никогда не изменяете содержимое строки. Мы знаем, что существует индекс n, в котором значение \0.

Итак, мы можем переписать его как:

for (scout = 0,offset = 0; scout < n; ++scout, ++offset)
    for (start = offset; *start < n; ++start)
        //single statement

(Я предположил, что строка начинается с адреса памяти 0), но поскольку это только сдвиг, что разрешено, это упрощает рассуждение об этом.

Теперь мы будем вычислять количество операторов во внутреннем цикле for (параметризован). Это равно:

С o смещение и n длина строки.

Теперь мы можем использовать эту формулу для вычисления количества команд на внешнем уровне for -loop. Здесь o начинается с 0 и выполняет итерацию (исключая) n. Таким образом, общее количество инструкций:

Что такое O (n ^ 2).

Но теперь нужно спросить: возможно ли построить такую ​​строку? Ответ нет! Имеются только 255 допустимые символы (символ NUL не считается символом); если мы не сможем сделать это предположение, то это верно. Скажем, первый символ - это a (с произвольным char), затем он либо совпадает с другим a в строке, который может быть разрешен в O (n) времени (цикл через оставшуюся часть строки ); или это означает, что все остальные символы отличаются от a. В первом случае алгоритм заканчивается на O (n); во втором случае это означает, что второй символ отличается.

Скажем, второй символ b. Затем мы снова перебираем строку в O (n), и если она находит другую b, мы завершаем после шагов 2n или O (n). Если нет, нам нужно попытаться найти соответствие для следующего символа c.

Дело в том, что нам нужно сделать это не более 255 раз: потому что есть только 255 допустимых символов. В результате сложность времени равна 255n или O (n).

Альтернативное объяснение

Другим вариантом этого объяснения является "если внешний цикл for ищет i-го символа, который мы знаем, что все символы слева от i, отличаются от этого символа (в противном случае мы бы уже отбросили ранее)". Теперь, поскольку есть только символы 255 и все символы слева отличаются друг от друга и текущего символа, мы знаем, что для 256 -го символа строки мы больше не можем найти новый персонаж, потому что таких символов нет.

Пример

Скажем, у вас есть алфавит с символами 3 (a, b и c) - это только для того, чтобы было легче понять суть вопроса. Теперь скажем, что у нас есть строка:

scout
v
b a a a a a b
  ^
  start

Понятно, что ваш алгоритм будет использовать шаги O (n): start будет просто перебирать всю строку один раз, достигать b и возвращаться.

Теперь скажите, что в строке нет дубликата b. В этом случае алгоритм не останавливается после однократного повторения строки. Но это означает, что все остальные символы должны отличаться от (в конце концов, мы повторяем строку и не нашли дубликата). Итак, теперь рассмотрим строку с этим условием:

scout
v
b a a a a a a
  ^
  start

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

  scout
  v
b a a a a a a
    ^
    start

И начнет поиск a. Здесь нам очень повезло: первый символ - a. Но если есть дубликат a; это будет стоить не более двух итераций, поэтому O (2n) найдет дубликат.

Теперь мы достигли связанного случая: нет a. В этом случае мы знаем, что строка должна начинаться с

    scout
    v
b a c ...

Кроме того, мы знаем, что оставшаяся часть строки не может содержать b и a, потому что в противном случае scout никогда не сдвинулся бы так далеко. Единственная оставшаяся возможность состоит в том, что остаток строки содержит c 's. Поэтому строка читает:

    scout
    v
b a c c c c c c c c c c
      ^
      start

Это означает, что после итерации по строке не более 3 раз мы найдем такой дубликат, независимо от размера строки, или того, как символы распределяются между этой строкой.

Изменить это на O (1) раз

Вы можете легко изменить этот алгоритм, чтобы он работал в O (1) раз: просто поместите дополнительные оценки по индексам:

int strunique(const char *str)
{
    size_t offset = 1;
    char *scout = (char *)str, *start, *stop = scout+255;

    for (; scout < stop && *scout != '\0'; ++scout, ++offset)
        for (start = (char *)str + offset; start <= stop && *start != '\0'; ++start)
            if (*start == *scout)
                return 0;

    return 1;
}

В этом случае мы ограничили первый цикл таким образом, чтобы он посещал не более 255 символов, внутренний цикл посещает только первый 256 (обратите внимание на <= вместо <). Таким образом, общее число шагов ограничено 255 x 256 или O (1). В приведенном выше объяснении уже показано, почему этого достаточно.

Примечание. Если это c, вам нужно заменить 255 на 4'294'967'296, что делает его действительно теоретически O (n), но практически O (n ^ 2) в смысл, что постоянный множитель до n является огромным для O (n), что O (n ^ 2) превосходит его.

Поскольку мы объединяем проверку завершения строки с помощью 256 -check, этот алгоритм будет работать почти всегда быстрее, чем предложенный выше. Единственным источником потенциально дополнительных циклов является дополнительное тестирование, которое поставляется с модифицированным for -loops. Но поскольку это приводит к более быстрому завершению, во многих случаях это не приведет к дополнительному времени.

Big-ой

Можно сказать: "Да, это верно для строк с длиной, большей или равной 256 символам". "Что относительно строк размером менее 256?". Дело в том, что большой-ой анализ имеет дело с асимптотическим поведением. Даже если поведение было суперэкспоненциальным для некоторых строк, меньших или равных определенной длине, вы не учитываете их.

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

int strunique(const char *str) {
    return 0;
}

Он всегда возвращает false; потому что "существует длина n ₀ такая, что для каждой входной длины n > n ₀ этот алгоритм вернет правильный результат". Это не имеет особого отношения к самому большому-о-ому, это еще раз иллюстрирует, что нужно быть осторожным, говоря, что алгоритм, работающий в O (1), будет превосходить алгоритм в O (n ^ 6) для любого разумного ввода. Иногда постоянный фактор может быть гигантским.

Ответ 4

Ваш алгоритм O(N^2). Это легко понять, просто отметив, что в худшем случае строка со всеми уникальными символами, каждый символ должен быть проверен на каждый символ, который появляется после него. То есть, худшие, N*(N-1)/2 = O(N^2) сравнения.

Обратите внимание, что по определению:

f(x) = O(g(x))

если существует такая константа, что |f(x)| <= M|g(x)| для всех достаточно больших x. Поэтому, когда вы говорите f(x) = O(n + 1/2n) (что неверно для вашего алгоритма), следует, что:

  f(x) = O(n + 1/2n)
  f(x) <= M * (n + 1/2n) for some M, n_0 for n >= n_0, by definition
  f(x) <= (3/2 * M) n, n >= n_0
  f(x) <= M' n, setting M' = 3/2 M, n >= n_0
  f(x) = O(n), by definition

То есть константы всегда выпадают, поэтому вы можете услышать выражение о том, что константы не имеют значения (по крайней мере, до вычисления сложности выполнения - очевидно, они имеют значение для реальной производительности)

Ответ 5

Строка со всеми уникальными символами может иметь длину не более 255. В этом случае ваш алгоритм работает в O (1) раз.

Если строка содержит повторяющиеся символы, один из этих повторяющихся символов появляется в первых 255 элементах строки. Тогда худшим случаем является то, что первые 254 символа строки уникальны, а 255-й символ повторяется до конца строки. Затем ваш алгоритм работает в O (N) времени.

Вы можете гарантировать время O (1) для своего алгоритма, сначала проверив, превышает ли длина строки 255 и не сразу будет работать, если это так.

Все, что предполагает, что char принимает одно из 256 значений. Если вы обрабатываете количество символов в char как переменную C, то сложностями для вашего алгоритма являются O (C ^ 2) в случае, если строка содержит только уникальные символы O (NC) в случае, если строка содержит дубликаты, и вы можете гарантировать время O (C ^ 2), сначала проверив длину строки не больше C.

Оптимальным алгоритмом является O (min (N, C)), сначала проверяя, что строка не больше, чем C, а затем с использованием любого алгоритма обнаружения дублирования по времени.