верхняя граница, нижняя граница
Исключение нулевого указателя - это индикатор того, что вы используете объект, не инициализируя его.
Например, ниже - класс ученика, который будет использовать его в нашем коде.
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 ");
}
}
}
3 ответа
Подтверждение верхней границы означает, что вы доказали, что алгоритм будет использовать не более некоторого ограничения на ресурс.
Подтверждение нижней границы означает, что вы доказали, что алгоритм будет использовать не менее некоторого ограничения на ресурс.
«Ресурс» в этом контексте может быть временем, памятью, пропускной способностью или чем-то еще.
Верхняя и нижняя границы имеют отношение к минимальной и максимальной «сложности» алгоритма (я использую это слово заранее, поскольку оно имеет очень специфическое значение при анализе сложности).
Возьмите, к примеру, нашего старого друга, пузырьковую разновидность. В идеальном случае, когда все данные уже отсортированы, требуется время f (n), функция зависит от n, количества элементов в списке. Это потому, что вам нужно сделать только один проход набора данных (с нулевыми перестановками), чтобы убедиться, что ваш список отсортирован.
В особенно плохом случае, когда данные сортируются в порядке, обратном желаемому, требуемое время становится f (n 2 ). Это происходит потому, что каждый проход перемещает один элемент в нужную позицию, и вам нужно n проходов, чтобы выполнить все элементы.
В этом случае верхняя и нижняя границы различны, хотя сложность big-O остается неизменной.
Кроме того, пузырьковая сортировка сильно порочна (обычно по уважительным причинам), но может иметь смысл в определенных обстоятельствах. Я на самом деле использую его в приложении, где большая часть данных уже отсортирована и только один или два элемента, как правило, добавляются за один раз в конец списка. Для добавления одного элемента и с пузырьковой сортировкой в обратном направлении вы можете гарантировать, что новый список будет отсортирован за один проход. Это иллюстрирует концепцию нижней границы.
Фактически, вы могли бы сделать оптимизацию пузырьковой сортировки, которая устанавливает нижнюю границу для f (1), просто предоставив дополнительную информацию, которая указывает, отсортирован ли список. Вы должны установить это после сортировки и очистить при добавлении элемента в конец.
Какой бы ни была граница (верхняя или нижняя), мы всегда говорим о входных данных в худшем случае, которые мы можем рассмотреть. Например, при сортировке мы предполагаем, что наихудшим случаем является несортированный список ввода.
Насколько я понимаю, задачи имеют нижнюю границу. Например, мы говорим, что нижняя граница сортировки на основе сравнения - \ Omega (n log n); мы не делаем никаких предположений о том, какой конкретный алгоритм сортировки на основе сравнения мы используем. Каким бы ни был алгоритм (сортировка слиянием, быстрая сортировка и т. Д.), Мы не можем добиться большего успеха, чем эта граница \ Omega (n log n). Нижние границы интуитивно говорят нам, насколько сложна конкретная проблема .
Когда мы говорим о конкретном алгоритме , то говорим о верхних границах. Например, мы говорим, что верхняя граница сортировки пузырьков O (n ^ 2), а верхняя граница сортировки слиянием O (n log n). Верхние границы, интуитивно, говорят нам, насколько хорош конкретный алгоритм при решении задачи.