Как рассчитать порядок (большой O) для более сложных алгоритмов (например, быстрая сортировка)
Исключение нулевого указателя - это индикатор того, что вы используете объект, не инициализируя его.
Например, ниже - класс ученика, который будет использовать его в нашем коде.
public class Student {
private int id;
public int getId() {
return this.id;
}
public setId(int newId) {
this.id = newId;
}
}
Приведенный ниже код дает вам исключение с нулевым указателем.
public class School {
Student obj_Student;
public School() {
try {
obj_Student.getId();
}
catch(Exception e) {
System.out.println("Null Pointer ");
}
}
}
Поскольку вы используете Obj_Student, но вы забыли инициализировать его, как в правильном коде, показанном ниже:
public class School {
Student obj_Student;
public School() {
try {
obj_Student = new Student();
obj_Student.setId(12);
obj_Student.getId();
}
catch(Exception e) {
System.out.println("Null Pointer ");
}
}
}
6 ответов
Логарифм - это операция, обратная возведению в степень. Пример возведения в степень - это когда вы удваиваете количество элементов на каждом шаге. Таким образом, логарифмический алгоритм часто уменьшает вдвое количество элементов на каждом шаге. Например, бинарный поиск попадает в эту категорию.
Многие алгоритмы требуют логарифмического числа больших шагов, но каждый большой шаг требует O (n) единиц работы. Mergesort попадает в эту категорию.
Обычно вы можете идентифицировать подобные проблемы, визуализируя их в виде сбалансированного двоичного дерева. Например, вот сортировка слиянием:
6 2 0 4 1 3 7 5
2 6 0 4 1 3 5 7
0 2 4 6 1 3 5 7
0 1 2 3 4 5 6 7
Вверху находится вход в виде листьев дерева. Алгоритм создает новый узел, сортируя два узла над ним. Мы знаем, что высота сбалансированного двоичного дерева равна O (log n), поэтому существует O (log n) больших шагов. Однако создание каждой новой строки требует O (n) работы. O (log n) больших шагов работы O (n) означает, что в целом сортировка слиянием составляет O (n log n).
Обычно алгоритмы O (log n) выглядят так, как показано ниже. Они могут отбрасывать половину данных на каждом этапе.
def function(data, n):
if n <= constant:
return do_simple_case(data, n)
if some_condition():
function(data[:n/2], n / 2) # Recurse on first half of data
else:
function(data[n/2:], n - n / 2) # Recurse on second half of data
Алгоритмы O (n log n) выглядят как функция ниже. Они также разделяют данные пополам, но им нужно учитывать обе половины.
def function(data, n):
if n <= constant:
return do_simple_case(data, n)
part1 = function(data[n/2:], n / 2) # Recurse on first half of data
part2 = function(data[:n/2], n - n / 2) # Recurse on second half of data
return combine(part1, part2)
Где do_simple_case () занимает O (1) раз, а comb () занимает не более O (n) времени.
Алгоритмам не нужно разделять данные точно пополам. Они могли бы разделить его на одну треть и две трети, и это было бы хорошо. Для средней производительности достаточно разделить ее в среднем пополам (например, QuickSort). Пока рекурсия выполняется по частям (n / something) и (n - n / something), все в порядке.Если он разбивает его на (k) и (n-k), тогда высота дерева будет O (n), а не O (log n).
Посмотрите пример "телефонной книги", приведенный здесь: Каково простое английское объяснение обозначения "Big O"?
Помните, что Big-O - это все о масштабе : как гораздо больше операций потребует этот алгоритм по мере роста набора данных?
O (log n) обычно означает, что вы можете разрезать набор данных пополам с каждой итерацией (например, двоичный поиск)
O (n log n) означает, что вы выполняете операцию O (log n) для каждого элемента в вашем наборе данных
Я почти уверен, что «O (n log log n)» не имеет никакого смысла . Или, если это так, он упрощается до O (n log n).
Для некоторых алгоритмов получить жесткую границу времени работы с помощью интуиции почти невозможно (не думаю, что когда-нибудь смогу интуитивно понять O (n log log n) run времени, например, и я сомневаюсь, что кто-нибудь когда-нибудь от вас ожидает). Если вам удастся достать текст Введение в алгоритмы CLRS , вы найдете довольно тщательное рассмотрение асимптотической записи, которое является достаточно строгим, но не полностью непрозрачным.
Если алгоритм рекурсивный, один простой способ получить границу - это записать рекурсию, а затем приступить к ее решению, либо итеративно, либо с использованием Главной теоремы или каким-либо другим способом. Например, если вы не стремитесь быть очень строгими в этом вопросе, самый простой способ получить время работы QuickSort - это использовать основную теорему - QuickSort влечет за собой разделение массива на два относительно равных подмассива (должно быть довольно интуитивно понятно, чтобы увидеть, что это O (n) ), а затем рекурсивно вызывает QuickSort для этих двух подмассивов. Тогда, если мы позволим T (n) обозначить время работы, мы получим T (n) = 2T (n / 2) + O (n) , что согласно Мастер-методу O (n log n) .
При применении алгоритма «разделяй и властвуй», где вы разделяете проблему на подзадачи, пока она не станет настолько простой, что она станет тривиальной, если разбиение идет хорошо, размер каждой подзадачи равен n / 2 или около того. . Это часто является источником log (n) , который возникает при большой сложности O: O (log (n)) - это количество рекурсивных вызовов, необходимых, когда разбиение идет хорошо .
Я попытаюсь провести интуитивный анализ того, почему Mergesort имеет значение n log n, и если вы можете дать мне пример алгоритма n log log n, Я тоже могу с этим справиться.
Сортировка слиянием - это пример сортировки, который работает путем многократного разделения списка элементов до тех пор, пока не будут существовать только элементы, а затем объединения этих списков вместе. Основная операция в каждом из этих слияний - это сравнение, и каждое слияние требует не более n сравнений, где n - длина двух объединенных списков. Из этого вы можете получить повторение и легко решить его, но мы будем избегать этого метода.
Вместо этого подумайте, как будет вести себя Mergesort, мы возьмем список и разделим его, затем возьмем эти половины и снова разделим его, пока у нас не будет n разделов длиной 1. Я надеюсь, что это легко увидеть. эта рекурсия будет идти только в log (n), пока мы не разделим список на n разделов.
Теперь, когда у нас есть, что каждый из этих n разделов необходимо объединить, затем, как только они будут объединены, нужно будет объединить следующий уровень, пока мы снова не получим список длины n. См. Рисунок в Википедии для простого примера этого процесса http: //en.wikipedia.org / wiki / Файл: Merge_sort_algorithm_diagram.svg .
Теперь рассмотрим количество времени, которое займет этот процесс, у нас будет log (n) уровней, и на каждом уровне нам придется объединить все списки. Как оказалось, на объединение каждого уровня потребуется n раз, потому что мы будем объединять в общей сложности n элементов каждый раз. Тогда вы можете довольно легко увидеть, что для сортировки массива с помощью mergesort потребуется n log (n) времени, если вы примете операцию сравнения как наиболее важную операцию.
Если что-то неясно или я что-то пропустил, дайте мне знать, и я постараюсь быть более подробным.
Edit Second Explanation:
Дайте мне подумать, смогу ли я объяснить это лучше.
Проблема разбивается на кучу меньших списков, а затем меньшие списки сортируются и объединяются, пока вы не вернетесь к исходному списку, который теперь отсортирован.
Когда вы разбиваете задачи, у вас есть несколько разных уровней размера, сначала у вас будет два списка размеров: n / 2, n / 2, затем на следующем уровне у вас будет четыре списка размеров: n / 4 , n / 4, n / 4, n / 4 на следующем уровне у вас будет n / 8, n / 8, n / 8, n / 8, n / 8, n / 8, n / 8, n / 8 это продолжается до тех пор, пока n / 2 ^ k не станет равным 1 (каждое подразделение - это длина, деленная на степень 2, не все длины будут делиться на четыре, поэтому это будет не так красиво). Это повторяется деление на два и может продолжаться не более log_2 (n) раз, потому что 2 ^ (log_2 (n)) = n, поэтому любое дальнейшее деление на 2 приведет к списку нулевого размера.
Теперь важно отметить, что на каждом уровне у нас есть n элементов, поэтому для каждого уровня слияние займет n раз, потому что слияние - это линейная операция.Если существует log (n) уровней рекурсии, то мы выполним эту линейную операцию log (n) раз, поэтому время выполнения будет n log (n).
Извините, если это тоже не помогло.
Обычно вы можете требовать журнал n для алгоритмов, где он вдвое уменьшает пространство / время при каждом запуске. Хорошим примером этого является любой двоичный алгоритм (например, двоичный поиск). Вы выбираете либо влево, либо вправо, после чего искомое пространство разделяется пополам. Образец многократного выполнения половины - это log n.