Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Novichock123
1 / 1 / 0
Регистрация: 25.04.2015
Сообщений: 41
1

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

29.06.2015, 13:49. Просмотров 296. Ответов 1
Метки нет (Все метки)

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

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

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

Возникло пару вопросов
1) Что подразумевает под собой количество операций C*logn ?
2) Что подразумевает под собой количество операций http://www.cyberforum.ru/cgi-bin/latex.cgi?C_{n}?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.06.2015, 13:49
Ответы с готовыми решениями:

Оценить время выполнения и сложность простейших операций с разными типами данных
Меня интересует-вопрос: можно как-то оценить по-быстрому время, которое...

Составить структуру, которая имеет следующие поля
структура имеет следующие поля: фамилия, возраст, образование, должность....

Какую структуру имеет память, которая выделяется для работы программы на С++
Какую структуру имеет память которая выделяется для роботы программы на С++?

Заполнить структуру B которая содержит структуру A при условии тога что в A уже записано имя
Есть две структуры. struct A{ char name; char last; }; struct B{ char...

Реализовать программу, которая бы позволяла выполнить одну из следующий операций по выбору пользователя
Реализовать программу, которая бы позволяла выполнить одну из следующий...

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

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

Почему надо двигаться таким длинным путём, если можно сделать как обычный массив (или допустим односвязный список)?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.06.2015, 15:06

Сложность со считыванием данных из файла в массив
Программа должна по нажатию кнопки считывать из файла числа и записывать их в...

Поменять местами строчку которая имеет максимальный елемент со строкой которая имеет минимальный елемент.Вывести обе матрицы на екран!!
Данно квадратную матрицу А розмера NxN (N<=10), которая состоить с...

Реализовать все битовые операции
2. Битовые логические операции. Первое целое двоичное число «a» вводится на...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru