Sem I (Program I) - N4 Flashcards
Что такое Bubble Sort? и его характеристики:
1) Временная сложность
2) Пространственная сложность
3) Стабильность
4) Использование
Простой алгоритм сортировки, который повторно проходит по списку, сравнивает соседние элементы и меняет их местами, если они находятся в неправильном порядке. Проход по списку повторяется до тех пор, пока список не будет отсортирован. Алгоритм получил свое название из-за того, что меньшие элементы “всплывают” на вершину списка.
1) Временная сложность: O(n^2) в худшем и среднем случае.
2) Пространственная сложность: O(1) (сортировка на месте).
3) Стабильность: Да.
4) Использование: Лучше всего подходит для небольших наборов данных или когда набор данных почти отсортирован.
Что такое Selection Sort? и его характеристики:
1) Временная сложность
2) Пространственная сложность
3) Стабильность
4) Использование
Алгоритм сортировки методом прямого выбора, который делит входной список на две части: подсписок уже отсортированных элементов, который строится слева направо в начале списка, и подсписок элементов, остающихся для сортировки. Алгоритм неоднократно выбирает наименьший (или наибольший) элемент из неотсортированного подсписка, меняет его местами с самым левым неотсортированным элементом и передвигает границы подсписка на один элемент вправо.
1) Временная сложность: O(n^2) в худшем и среднем случае.
2) Пространственная сложность: O(1) (сортировка на месте).
3) Стабильность: Нет.
4) Использование: Полезно, когда ограничена память, так как требуется всего O(1) дополнительного пространства.
Что такое Insertion Sort? и его характеристики:
1) Временная сложность
2) Пространственная сложность
3) Стабильность
4) Использование
Простой алгоритм сортировки, который строит окончательный отсортированный массив (или список) по одному элементу за раз. Он намного менее эффективен на больших списках по сравнению с более продвинутыми алгоритмами, такими как быстрая сортировка, пирамидальная сортировка или сортировка слиянием. Однако на практике он более эффективен по сравнению с другими квадратичными алгоритмами сортировки, такими как пузырьковая сортировка или сортировка выбором.
1) Временная сложность: O(n^2) в худшем и среднем случае, но O(n) в лучшем случае, когда массив уже отсортирован.
2) Пространственная сложность: O(1) (сортировка на месте).
3) Стабильность: Да.
4) Использование: Полезно для небольших наборов данных или когда массив уже частично отсортирован.
Что такое Merge Sort? и его характеристики:
1) Временная сложность
2) Пространственная сложность
3) Стабильность
4) Использование
Эффективный стабильный алгоритм сортировки, основанный на сравнении и разделении.
1) Временная сложность: O(n log n) в худшем, среднем и лучшем случае.
2) Пространственная сложность: O(n) из-за необходимости временного массива.
3) Стабильность: Да.
4) Использование: Полезно для сортировки связанных списков и внешней сортировки (сортировка данных, которые слишком велики, чтобы поместиться в память).
Что такое Quick Sort? и его характеристики:
1) Временная сложность
2) Пространственная сложность
3) Стабильность
4) Использование
Внутренний, основанный на сравнении алгоритм сортировки. Он работает, выбирая элемент ‘опорный элемент’ из массива и разделяя остальные элементы на две подмножества, в зависимости от того, меньше они или больше опорного элемент. Затем подмножества сортируются рекурсивно.
1) Временная сложность: O(n^2) в худшем случае, O(n log n) в среднем.
2) Пространственная сложность: O(log n) из-за рекурсии.
3) Стабильность: Нет.
4) Использование: Один из самых широко используемых алгоритмов для больших наборов данных.
Что такое Heap Sort? и его характеристики:
1) Временная сложность
2) Пространственная сложность
3) Стабильность
4) Использование
На основе сравнения, использующий структуру данных двоичной кучи. Он похож на сортировку выбором, где мы сначала находим максимальный элемент и помещаем его в конец. Повторяем тот же процесс для оставшихся элементов.
1) Временная сложность: O(n log n) в худшем, среднем и лучшем случае.
2) Пространственная сложность: O(1) (сортировка на месте).
3) Стабильность: Нет.
4) Использование: Полезно, когда требуется хорошая производительность в худшем случае.
Что такое LinearSearch? и его характеристики:
1) Временная сложность
2) Пространственная сложность
3) Стабильность
4) Использование
Algorithm that checks every element in the list until it finds the target value.
1) Временная сложность O(n)
2) Пространственная сложность O(1)
4) Используется для небольших массивов или неотсортированных данных, где производительность не является критически важной.
Что такое BinarySearch? и его характеристики:
1) Временная сложность
2) Пространственная сложность
3) Стабильность
4) Использование
Eefficient algorithm for finding an item from a sorted list of items by repeatedly dividing the search interval in half.
1) Временная сложность O(log n)
2) Пространственная сложность O(1)
3) Стабильность - Нестабильный (может потребоваться изменение порядка элементов в рекурсивном варианте).
4) Используется для поиска в отсортированных массивах или списках.
O(1)
Время выполнения алгоритма не зависит от размера входных данных. Примеры включают доступ к элементу массива по индексу или проверка значения в хэш-таблице.
def get_first_element(arr):
return arr[0]
O(log n)
Выполнения алгоритма увеличивается логарифмически с увеличением входных данных. Часто встречается в алгоритмах бинарного поиска.
Что означает Логарифм размера входных данных?
Математическая функция, обратная возведению в степень.
Логарифм по основанию 2 от числа n обозначается как log2(n). Это число 𝑘, такое что 2^𝑘=𝑛.
Примеры:
- log2(1) = 0, потому что 2^0 = 1
- log2(2) = 1, потому что 2^1 = 2
- log2(4) = 2, потому что 2^2 = 4
- log2(8) = 3, потому что 2^3 = 8
- log2(16) = 4, потому что 2^4 = 16
O(n)
Время выполнения алгоритма растет линейно с увеличением размера входных данных.
O(n log n)
Часто встречается в алгоритмах сортировки, таких как быстрая сортировка и сортировка слиянием. Эти алгоритмы более эффективны, чем O(n²) алгоритмы для больших наборов данных.
O(n²)
Время выполнения алгоритма увеличивается квадратично с увеличением размера входных данных. Часто встречается в алгоритмах с вложенными циклами, например, в сортировке пузырьком или сортировке вставками.
InputStream (JAVA)
абстрактный класс, который используется для чтения байтов данных. Он находится в пакете java.io.
InputStream inputStream = new FileInputStream("file.txt");
int data = inputStream.read();
while (data != -1) {
System.out.print((char) data);
data = inputStream.read();
}
inputStream.close();
OutputStream (JAVA)
абстрактный класс, который используется для записи байтов данных. Он находится в пакете java.io.
OutputStream outputStream = new FileOutputStream("file.txt");
outputStream.write(65); // записывает символ 'A'
outputStream.close()
InputStreamReader (JAVA)
используется для чтения потоков ввода байтов и преобразования их в символы, используя указанную кодировку символов. Он является мостом между потоками байтов и потоками символов.
Ternary operator (JAVA)
Concise way to express conditional statements.
takes three operands.: condition ? expression1 : expression2
int a = 10;
int b = 20;
int max = (a > b) ? a : b;
System.out.println("The maximum value is " + max);
int num = 5; String result = (num % 2 == 0) ? "Even" : "Odd"; System.out.println(num + " is " + result);
int a = 10;
int b = 20;
int c = 30;
int max = (a > b) ? (a > c ? a : c) : (b > c ? b : c);
System.out.println("The maximum value is " + max);
System.in.read()
Позволяет читать байты из стандартного входного потока (обычно это консоль). Этот метод блокирует выполнение программы до тех пор, пока не будет введен хотя бы один байт. Он возвращает значение типа int, представляющее байт, который был прочитан, или -1, если достигнут конец потока.
import java.io.IOException;
public class ReadByte {
public static void main(String[] args) {
System.out.println("Введите символ:");
try {
int input = System.in.read();
System.out.println("Вы ввели: " + (char) input);
} catch (IOException e) {
System.err.println("Ошибка ввода-вывода: " + e.getMessage());
}
}
}
import java.io.IOException;
public class ReadUntilEOF {
public static void main(String[] args) {
System.out.println("Введите данные (для завершения нажмите Ctrl+D или Ctrl+Z):");
try {
int input;
while ((input = System.in.read()) != -1) {
System.out.print((char) input);
}
} catch (IOException e) {
System.err.println("Ошибка ввода-вывода: " + e.getMessage());
}
}
}
BufferedReader (JAVA)
Используется для более эффективного чтения текста из потока ввода, который может быть файла, клавиатуры или другого источника. Он оборачивает Reader и использует буфер для чтения больших блоков данных за один раз, что увеличивает производительность при чтении.
read(): Читает один символ
read(char[] cbuf, int off, int len): Читает символы в массив
readLine(): Читает одну строку текста.
close(): Закрывает поток и освобождает ресурсы.
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
public class BufferedReaderExample {
public static void main(String[] args) {
try (BufferedReader br = new BufferedReader(new FileReader("example.txt"))) {
String line;
while ((line = br.readLine()) != null) {
System.out.println(line);
}
} catch (IOException e) {
e.printStackTrace();
}
}
}
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class BufferedReaderExample {
public static void main(String[] args) {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Введите строку текста:");
try {
String input = br.readLine();
System.out.println("Вы ввели: " + input);
} catch (IOException e) {
e.printStackTrace();
}
}
}
