vadimr

Очевидно, да. Чтобы доказать утверждение по индукции, вам надо из индукционного предположения P(k) доказать P(k+1). Если P(k+1) состоит из кучи частей Pi(k+1), то надо их все доказать. Ведь иначе у вас P(k+1) окажется истинным лишь частично, а значит вы индукционный шаг не доказали.
Если вам надо доказать, что "все овцы имеют 4 белые ноги", а вы выводите, только "у них 4 ноги", то вы не доказали исходное утверждение, ибо из "4 ноги" не следует "4 белых ноги". Может быть, у них 4 черных ноги.

Да, именно удалять — возможно. А вот скорость удаления данных с диска зависит от скорости работы накопителя. Для полного удаления данных необходимо полностью обнулить каждую ячейку памяти в накопителе. По умолчанию ОС удаляет только запись о файле в ФС, а вот содержимое файла остаётся и будет перезаписано когда-нибудь в будущем, когда дойдёт очередь до данного сектора/ячейки памяти. Кроме того, для более надёжного удаления данных с HDD используется многократная запись, чтобы не осталось даже остаточного заряда, который теоретически можно считать. Есть даже специальные приложения для удаления данных с дисков с многократной записью в каждую ячейку. Аналогично и для шифрования — надо сначала считать данные с диска, зашифровать их, записать на диск и только потом удалить оригинальные данные.

Единственное, что может очень быстро удалить данные с диска — устройства для физического уничтожения дисков. Для HDD используются мощные электромагниты. С SSD несколько сложнее, т.к. там используется флеш-память: тут уже требуется физическое разрушение микросхем — измельчить в специальном шредере очень мелко, разогреть больше сотни-полутора градусов, сжечь электромагнитным импульсом (из разряда экзотики конечно же - ибо куда сложнее и есть риск сжечь чего лишнего). Так же существуют специальные SSD со встроенным механизмом уничтожения.

Не с того начали обсуждение :) Обсуждение вопроса защиты информации всегда начинается с обсуждения модели нарушителя. То есть с ответа на вопрос "какую ситуацию я хочу предотвратить и от кого защититься". Потому что разные категории "кого" имеют разные возможности в том числе и в отношении "наплевать на закон и состояние здоровия".

Никакое шифрование Вас не спасет от государства - данные оно может быть и не получит, но Вам в любом случае обеспечит бесплатную путевку в страну вечной зимы лет так на ... "Содействие терроризму" - и привет.

Никакое шифрование вас не спасет от гопоти - опять же данные она может быть и не получит, но с помощью паяльника может изрядно попортить Вам здоровье

Поэтому рассмотрение вопроса надо начинать с конкретизации задачи - кто защищает, что защищает, от кого защищает. Технические-то средства есть - это крайне мощный ЭМИ. Неудобство в том, что отлаживать сложно, ибо он сжигает не только ssd, но и все вокруг :D

Никак не называется. Можно структуры комбинировать для ваших задач, но это частные случаи применения структур, не настолько частые, чтобы давать этой комбинации какое-то имя. Если уж хочется назвать это как-то, то это все еще будет хеш-таблица с какими-то вспомагательными пристройками для каких-то дополнительных нужных вам свойств (итерация).

И вообще, у вас тут намудрено, почему нельзя сделать просто:
let objects: HashMap<Uuid, Object>;

Тут все такой же O(1) доступ к элементу по id. Зачем вам массив? Вы там добились простой и cache-friendly итерации по всем объектам? Не факт, что это уже не реализовано внутри HashMap. По крайней мере во многих языках можно проитерироваться по всем объектам в стандартной хеш-таблице.

Зато у вас там удаление элемента - это что-то сложное. Особенно, если вы не хотите избежать фрагментации и неиспользованного места в массиве.

Да, можно. Для этого надо в качестве pivot'а выбрать медиану. если это сделать за O(n) в худшем случае, то общая сложность QuickSort'а будет O(n log n).

Для выбора медианы за O(n) есть, например, вот такой алгоритм. В каких-то источниках его еще называли алгоритмом кнута-пратта-мориса-ривеста-тарьяна. Кажется, но я их найти не могу, так что я какие-то фамилии напутал, но помню, что там было 5 великих информатиков.

На практике же это не применяют, потому что этот алгоритм хоть и имеет линейную сложность в худшем, константа там такая, что там на квадрат хватит и еще на логарифм сверху останется. Просто используя какие-нибудь случайные числа можно добиться гораздо лочшей производительности.

Доказательство не верно из-за индуктивного перехода. Вы рассматриваете только уже отсортированные наборы задач. Не ясно, что добавляя задачи в другом порядке вы получаете варианты не лучше. Вы так же не показали, что вот эти 2 варианта дают оптимальное время для k+1 задачи.

Правильное доказательство весьма простое и без индукции. Общее время будет

Max(sum{i-начальнику}(bi), max{i - подчиненным}(ai))

.
Отсюда видно, что если вы какую-то задачу дали подчиненному, то все задачи с меньшим A нет смысла давать начальнику. Ведь второе слагаемое-максимум от этого не изменится, но первое увеличится. Можно "бесплатно" выполнить эти задачи подчиненными. Поэтому в оптимальном ответе вы даете какое-то множетсво минимальных A подчиненым, а остальные начальнику. Иначе можно какие-то задачи перекинуть с начальника на подчиненного и уменьшить первое слагаемое не меняя второе, уменьшив таким образом ответ, т.е. в этом случае решение точно не оптимальное.
Чтобы все варианты возможных оптимумов перебрать надо отсортировать задачи по возрастанию A. Это код и делает. поддерживается сумма B у всех оставшихся задач, а от текущей берется A - который и будет максимумом для всех задач с меньшим A.