Сложность вычислений
Прежде всего, из вашего вопроса, я понимаю, что будет хорошо быстро объяснить time complexity и big oh notation.
Цитата из wikipedia :
В информатике сложность времени - это сложность вычислений, которая описывает количество времени, необходимое для запуска алгоритма. Временная сложность обычно оценивается путем подсчета количества элементарных операций, выполняемых алгоритмом, предполагая, что каждая элементарная операция занимает фиксированное количество времени для выполнения. [...] Поскольку время выполнения алгоритма может варьироваться среди разных входов одного и того же размера, обычно учитывается сложность времени наихудшего случая, которая представляет собой максимальное количество времени, необходимое для входов данного размера.
Большая O-нотация
Алгоритмы c Сложности классифицируются в соответствии с типом функции, появляющейся в большой O-нотации. Например, алгоритм с временной сложностью O (n). O (n) - это алгоритм линейного времени, а алгоритм с временной сложностью O (n ^ alpha) для некоторой константы alpha> 1 - это алгоритм полиномиального времени.
В отношении двух примеров кода
Посмотрите на два примера кода. Сразу заметим несколько вещей:
- Размер кода в образце 1 намного меньше. Так что, возможно, у нас может быть меньше операций.
- Что еще более важно, мы заметили вложенный for-l oop во втором примере. Первый образец не имеет. Это не обязательно снижает стоимость кода внутри методов.
Давайте проведем небольшой эксперимент. Давайте посчитаем количество операций, необходимых в средне-плохой ситуации (первый неповторяющийся символ посередине), когда size of Z is = 1, 10, 100, and 1000.
Примечание: в этом примере / мысленном эксперименте I оценит каждую строку как операцию затрат 1. Это грубое упрощение. Прошу прощения за любые подсчеты количества операций.
Algorithm 1: (size of s, lines executed)
-
1, 3
10, (2*5)+1 = 11
100, (2*50)+1 = 101
1000, (2* 500) + 1 = 1001
Total = (2* N/2 ) + 1
Мы видим, что результирующее количество выполнений линейно связано с начальным размером ввода.
Algorithm 2: (N = size of s, lines executed)
-
1, 7
10, 2(5*5) + 2
100, 2(50*50) + 2
1000, 2(500*500) + 2
Total = ((N/2) *2 + 2*(N/2)*(N/2) + 2
В логе 1 мы видим, что сложность линейно связана с размером ввода из конкретно O(n). В алгоритме 2 мы видим, что это полиномиальное время, а именно O(n^2). Однако это становится неправильным, если принять во внимание реальную стоимость indexOf и lastIndexOf.
Добавление стоимости indexOf и LastIndexOf
Let n=Size of the String S
Алгоритм 1: (грубо оценено Количество операций
for(int i=0;i<s.length(); i++) // - N/2
if(s.indexOf(s.charAt(i)) == s.lastIndexOf(s.charAt(i))) { // ~ worst case = (N/2 + N/2) * N/2
return s.charAt(i); // 1 operation
Total = N/2 + (N/2 + N/2)*N/2 +1
= N^2/2 + N/2 + 1
Алгоритм 2: (Примерно число операций)
for(int i=0;i<s.length(); i++) { // - executed N/2 times
int count = 0; // - executed N/2 times
for(int j=s.length()-1;j>=0; j--) { // Executed (n/2 * n/2 )
if(s.charAt(i) == s.charAt(j)) { // Executed (n/2 * n/2 )
count++; // Executed 1 time
}
}
if(count == 1) { //Evaluated N/2 times
return s.charAt(i); // Executed 1 time
}
}
return '_';
Total = N/2 + N/2 + 2(N/2*N/2) + 1
= N^2/2 + N + 1
Примечания: Я сделал несколько упрощений. Я также предположил, что неповторяющийся символ будет расположен в центре (n / 2) строки (символьный массив). Главное, что нужно принять, это то, что число выполненных операций увеличивается с увеличением размера. Приведенный выше пример призван доказать свою точку зрения. Не быть на 100% точным.
Кроме того, весь результат / аргумент, как указано в комментариях, - это то, как мы рассматриваем indexOf и lastIndexof. Считаем ли мы их как отдельные операции? Или мы рассматриваем их как операции N / 2? Это также зависит от реализации indexOf и lastIndexOf. Если они ищут в массиве, они прячут for loops внутри. В том случае, если они это делают (последний пример), стоимость обоих алгоритмов становится намного более похожей.
Algo1: N^2/4 + N/2 + 1
VS
Algo2: N^2/2 + N + 1