Почему метод 2 быстрее, чем метод 1, даже если метод 2 использует временную сложность O (2n), а метод 1 решает ту же проблему за O (n)
Решал проблему Элемент большинства GFG. У меня была такая же проблема с двумя подходами
Method 1
static int majorityElement1(int a[], int size) {
HashMap<Integer, Integer> mp = new HashMap<>();
int count = 0;
int maxNum = 0;
for (int i = 0; i < a.length; i++) {
if (mp.containsKey(a[i])) {
if (count < mp.get(a[i]) + 1) {
count = mp.get(a[i]) + 1;
maxNum = a[i];
}
mp.replace(a[i], mp.get(a[i]) + 1);
} else {
if (count < 1) {
count = 1;
maxNum = a[i];
}
mp.put(a[i], 1);
}
}
return (mp.get(maxNum) > size / 2) ? maxNum : -1;
}
Method 2
static int majorityElement(int a[], int size) {
int count = 0;
int maxNum = 0;
for (int i = 0; i < a.length; i++) {
if (count == 0) {
maxNum = a[i];
count++;
} else {
if (maxNum == a[i]) {
count++;
} else {
count--;
}
}
}
count = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] == maxNum) {
count++;
}
}
return (count > size / 2) ? maxNum : -1;
}
Даже мыслительный метод 1 решает проблему в На). Компилятор времени временной сложности GFG показывает, что лимит времени превышен. Но он показывает исполнение успешно, когда я использую код метода 2, временная сложность которого равна O (2n). Не могли бы вы помочь мне понять, как это происходит?
O(2n) == O(n)! Постоянные факторы не учитываются.
и это одна из проблем этой нотации: 100000n хуже, чем 1n, несмотря на такую же сложность (использование HashMap и поиск в нем, безусловно, требует дополнительного времени)
Как работает второй алгоритм?
Ответы 1
Обозначение Big O дает вам представление о росте с помощью «некоторого n». Это необходимо для правильного понимания используемых вами алгоритмов.
Учитывая это, вы не видите здесь общей картины. Как только вы знаете, что алгоритм находится в O (n) по сравнению с другим, который находится в O (2n), вы в основном говорите, что оба алгоритма растут с линейной скоростью, на самом деле постоянные коэффициенты поглощаются, поэтому оба они находятся в O ( п). Вы не можете точно знать, с какой скоростью, но вам придется копать больше.
Копать означает начать рассматривать дополнительные детали, такие как:
- сколько раз мы читаем значение из памяти?
- сколько обменов мы выполняем?
Например, для примера рассмотрим следующий сценарий: вы выполняете алгоритм, который должен менять местами записи в массиве для его сортировки. Это может быть неэффективно, поскольку вы выполняете много операций чтения и записи. Вы придумываете сопоставимый алгоритм, который выделяет другой массив, чтобы минимизировать такие свопы. Последняя версия более эффективна, но при этом использует больше памяти. Память не входила в первоначальный анализ.
Таким образом, нотация Big-O дает вам представление для грубых сравнений, затем вы должны проанализировать свои входные и выходные данные, чтобы понять, в чем на самом деле происходит рост: вы можете использовать неэффективный алгоритм для сортировки 10 элементов, но вы, возможно, не захотите делать то же самое с 100000.
В Википедии есть очень подробная и исчерпывающая статья здесь. Возможно, вы захотите взглянуть на него, это может помочь вам лучше понять предмет.
временная сложность не означает фактическую скорость выполнения. Это просто способ сравнить алгоритмы, поскольку
nстановится все больше и больше.