Реализовать структуру данных, которая имеет все те же операции, что массив длины n. Сложность операций

@Novichock123 · Регистрация: 25.04.2015

Author24 — интернет-сервис помощи студентам

Реализовать структуру данных, которая имеет все те же операции, что массив длины n, а именно

начать работу
положить в i-ю ячейку число n
узнать, что лежит в i-ой ячейке

а также операцию "указать номер минимального элемента" (или одного из минимальных элементов). Количество действий для всех операций должно быть не более C*log n, не считая операции "начать работу" (которая требует не более $https://www.cyberforum.ru/cgi-bin/latex.cgi?C_{n}$ действий).

Возникло пару вопросов
1) Что подразумевает под собой количество операций C*logn ?
2) Что подразумевает под собой количество операций $https://www.cyberforum.ru/cgi-bin/latex.cgi?C_{n}$ ?

@Novichock123 · 29.06.2015, 15:06 **[ТС]**

Реализовать структуру данных, которая имеет все те же операции, что массив длины n, а именно
• начать работу;
• положить в i-ю ячейку число x;
• узнать, что лежит в i-ой ячейке;
а также операцию
• указать номер минимального элемента (точнее, одного из минимальных элементов). Количество действий для всех операций должно быть не более C log n, не считая операции "начать работу" (которая требует не более Cn действий).
Решение. Используется приём, изложенный в разделе о сортировке деревом. Именно, надстроим над элементами массива как над листьями двоичное дерево, в каждой вершине которого храним минимум элементов соответствующего поддерева. Корректировка этой информации, а также прослеживание пути из корня к минимальному элементу требуют логарифмического числа действий.

Взято из А.Шень Программирование:теоремы и задачи

Почему надо двигаться таким длинным путём, если можно сделать как обычный массив (или допустим односвязный список)?

@Novichock123 1 / 1 / 0 Регистрация: 25.04.2015 Сообщений: 41
		1
	Реализовать структуру данных, которая имеет все те же операции, что массив длины n. Сложность операций 29.06.2015, 13:49. Показов 753. Ответов 1 Метки нет (Все метки) Реализовать структуру данных, которая имеет все те же операции, что массив длины n, а именно начать работу положить в i-ю ячейку число n узнать, что лежит в i-ой ячейке а также операцию "указать номер минимального элемента" (или одного из минимальных элементов). Количество действий для всех операций должно быть не более Clog n, не считая операции "начать работу" (которая требует не более $https://www.cyberforum.ru/cgi-bin/latex.cgi?C_{n}$ действий). Возникло пару вопросов 1) Что подразумевает под собой количество операций Clogn ? 2) Что подразумевает под собой количество операций $https://www.cyberforum.ru/cgi-bin/latex.cgi?C_{n}$ ? 0

@Novichock123 1 / 1 / 0 Регистрация: 25.04.2015 Сообщений: 41
	29.06.2015, 15:06 [ТС]	2
	Реализовать структуру данных, которая имеет все те же операции, что массив длины n, а именно • начать работу; • положить в i-ю ячейку число x; • узнать, что лежит в i-ой ячейке; а также операцию • указать номер минимального элемента (точнее, одного из минимальных элементов). Количество действий для всех операций должно быть не более C log n, не считая операции "начать работу" (которая требует не более Cn действий). Решение. Используется приём, изложенный в разделе о сортировке деревом. Именно, надстроим над элементами массива как над листьями двоичное дерево, в каждой вершине которого храним минимум элементов соответствующего поддерева. Корректировка этой информации, а также прослеживание пути из корня к минимальному элементу требуют логарифмического числа действий. Взято из А.Шень Программирование:теоремы и задачи Почему надо двигаться таким длинным путём, если можно сделать как обычный массив (или допустим односвязный список)? 0