2 задачки для разминки мозга

@Skyper · Регистрация: 04.11.2014

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

Задача 1) Массив состоит из 2 отсортированных массивов, приписанных друг за другом. Все элементы массива различны, его размер-n. Как найти заданный элемент в массиве за O(logn)?
Пример массива: 1 2 4 6 7 3 9 11 12 14 16 17 20 21
Задача 2) Описать саморасширяющийся массив, время добавления/удаления всегда O(logn)

@~~I-N-K~~ · 17.03.2015, 16:09

Сообщение от Skyper

Задача 1) Массив состоит из 2 отсортированных массивов, приписанных друг за другом. Все элементы массива различны, его размер-n. Как найти заданный элемент в массиве за O(logn)?

Бинарный поиск должен найти за O(long)

@salam · 18.03.2015, 10:15

1) Вы уверены, что это можно сделать?

@Qwertiy · 18.03.2015, 14:16

Сообщение от Skyper

2) Описать саморасширяющийся массив, время добавления/удаления всегда O(logn)

Декартово дерево с неявным ключом.

@Skyper · 19.03.2015, 18:25 **[ТС]**

Нам не известны границы 2 изначальных массивов, только размер нового

@Qwertiy · 19.03.2015, 20:01

Хочется как-то применить бинарный или тернарный поиск.

@SungMaster · 23.03.2015, 18:35

Задача 2) Описать саморасширяющийся массив, время добавления/удаления всегда O(logn)

2-3 дерево

@Igor3D · 24.03.2015, 14:13

Сообщение от Skyper

Задача 1) Массив состоит из 2 отсортированных массивов, приписанных друг за другом. Все элементы массива различны, его размер-n. Как найти заданный элемент в массиве за O(logn)?

Никак, сложность поиска в таком массиве превышает O(logn). Пример
Массив 1, 7, 2, 3, 4, 5, 9 Найти 7 (ну или 6 с ответом "такого нет")
При использовании двоичного поиска мы попадаем в правый массив, когда поиск в нем закончен - число сравнений уже log. А поиск "границы" обойдется "в ту же цену". А если не делить пополам (а что-то другое) - то уже не log

Сообщение от Skyper

Задача 2) Описать саморасширяющийся массив, время добавления/удаления всегда O(logn)

Не знаком с термином "саморасширяющийся массив", что это?

@salam · 24.03.2015, 14:31

Сообщение от Igor3D

Не знаком с термином "саморасширяющийся массив", что это?

некоторая СД, которая умеет эффективно отвечать на запросы "вставить элемент на i-ое место" и "вернуть i-ый элемент" / "посчитать что-то на отрезке текущего массива [l; r]".

@Qwertiy · 24.03.2015, 22:33

Сообщение от Igor3D

Никак, сложность поиска в таком массиве превышает O(logn).

Не согласен. log на поиск границы и для каждой части бинарный поиск.
Только вот я ещё не придумал, как границу найти...

Задача 2)

Тут уже 2 варианта предложено.

@Dimension · 25.03.2015, 19:38

1 бинпоиск
2 биндерево

Добавлено через 3 минуты
ах да,первую задачу за логн скорей всего не решить

@Skyper · 26.03.2015, 13:51 **[ТС]**

Во 2 задаче, на самом деле, подходит почти любая структура-дерево.

Пояснение к 1 задаче-O(logn)-это может быть и 3*log(3, n). Я думал над поиском границы(стык элементов, которого может и не быть т.е. массив идет так: 123(стык)56789) за logn, но так и не придумал. После этого бинпоиск по каждой части. Возможно, стык искать не нужно, а думать надо хитрее

@Qwertiy · 26.03.2015, 15:17

А если тернарный поиск вместо бинарного? Правда, я вообще не думал, как применить его...
То что мы ищем гарантированно есть в массиве, или не обязательно?
Других условий на массив нет, например, что он является перестановкой?

@Skyper · 26.03.2015, 17:12 **[ТС]**

Все элементы массива различны-думаю, это надо как-то учитывать.
С тернарником непонятно-этот элемент может быть "пропастью", например на массиве {1 2 5 7 9 1 10}, при индексации с 0, мы возьмем элементы на 2 и 4 позиции, т.е. 5 и 7, и пойдет троичный поиск от 0 до 4.
Массив не является перестановкой, просто все элементы различны

@Shamil1 · 26.03.2015, 18:12

1) по-моему, не решается

Возьмём отсортированный массив и добавим в него число Х на произвольную позицию. Как теперь найти X за O(logn)?
По-моему, никак. Чтобы найти X придётся проверить все элементы массива. Тот факт, что до добавления Х массив был отсортирован, нам никак не помогает.
А получившийся новый массив можно рассматривать как два отсортированных массива из условия задачи. Х будет либо последним элементом первого отсортированного массива, ли первым элементом второго.

@Skyper 0 / 0 / 0 Регистрация: 04.11.2014 Сообщений: 11
		1
	2 задачки для разминки мозга 16.03.2015, 23:00. Показов 1323. Ответов 14 Метки нет (Все метки) Задача 1) Массив состоит из 2 отсортированных массивов, приписанных друг за другом. Все элементы массива различны, его размер-n. Как найти заданный элемент в массиве за O(logn)? Пример массива: 1 2 4 6 7 3 9 11 12 14 16 17 20 21 Задача 2) Описать саморасширяющийся массив, время добавления/удаления всегда O(logn) 0

@~~I-N-K~~ Заблокирован
	17.03.2015, 16:09	2
	Сообщение от Skyper Задача 1) Массив состоит из 2 отсортированных массивов, приписанных друг за другом. Все элементы массива различны, его размер-n. Как найти заданный элемент в массиве за O(logn)? Бинарный поиск должен найти за O(long) 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	18.03.2015, 10:15	3
	1) Вы уверены, что это можно сделать? 0

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	18.03.2015, 14:16	4
	Сообщение от Skyper 2) Описать саморасширяющийся массив, время добавления/удаления всегда O(logn) Декартово дерево с неявным ключом. 0

@Skyper 0 / 0 / 0 Регистрация: 04.11.2014 Сообщений: 11
	19.03.2015, 18:25 [ТС]	5
	Нам не известны границы 2 изначальных массивов, только размер нового 0

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	19.03.2015, 20:01	6
	Хочется как-то применить бинарный или тернарный поиск. 0

@SungMaster 1 / 1 / 0 Регистрация: 25.10.2010 Сообщений: 29
	23.03.2015, 18:35	7
	Задача 2) Описать саморасширяющийся массив, время добавления/удаления всегда O(logn) 2-3 дерево 0

@Igor3D 1824 / 732 / 99 Регистрация: 01.10.2012 Сообщений: 3,748
	24.03.2015, 14:13	8
	Сообщение от Skyper Задача 1) Массив состоит из 2 отсортированных массивов, приписанных друг за другом. Все элементы массива различны, его размер-n. Как найти заданный элемент в массиве за O(logn)? Никак, сложность поиска в таком массиве превышает O(logn). Пример Массив 1, 7, 2, 3, 4, 5, 9 Найти 7 (ну или 6 с ответом "такого нет") При использовании двоичного поиска мы попадаем в правый массив, когда поиск в нем закончен - число сравнений уже log. А поиск "границы" обойдется "в ту же цену". А если не делить пополам (а что-то другое) - то уже не log Сообщение от Skyper Задача 2) Описать саморасширяющийся массив, время добавления/удаления всегда O(logn) Не знаком с термином "саморасширяющийся массив", что это? 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	24.03.2015, 14:31	9
	Сообщение от Igor3D Не знаком с термином "саморасширяющийся массив", что это? некоторая СД, которая умеет эффективно отвечать на запросы "вставить элемент на i-ое место" и "вернуть i-ый элемент" / "посчитать что-то на отрезке текущего массива [l; r]". 0

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	24.03.2015, 22:33	10
	Сообщение от Igor3D Никак, сложность поиска в таком массиве превышает O(logn). Не согласен. log на поиск границы и для каждой части бинарный поиск. Только вот я ещё не придумал, как границу найти... Задача 2) Тут уже 2 варианта предложено. 0

	26.03.2015, 18:12

@Dimension Dimension 594 / 462 / 223 Регистрация: 08.04.2014 Сообщений: 1,710
	25.03.2015, 19:38	11
	1 бинпоиск 2 биндерево Добавлено через 3 минуты ах да,первую задачу за логн скорей всего не решить 0

@Skyper 0 / 0 / 0 Регистрация: 04.11.2014 Сообщений: 11
	26.03.2015, 13:51 [ТС]	12
	Во 2 задаче, на самом деле, подходит почти любая структура-дерево. Пояснение к 1 задаче-O(logn)-это может быть и 3*log(3, n). Я думал над поиском границы(стык элементов, которого может и не быть т.е. массив идет так: 123(стык)56789) за logn, но так и не придумал. После этого бинпоиск по каждой части. Возможно, стык искать не нужно, а думать надо хитрее 0

@Qwertiy 833 / 641 / 101 Регистрация: 20.08.2013 Сообщений: 2,524
	26.03.2015, 15:17	13
	А если тернарный поиск вместо бинарного? Правда, я вообще не думал, как применить его... То что мы ищем гарантированно есть в массиве, или не обязательно? Других условий на массив нет, например, что он является перестановкой? 0

@Skyper 0 / 0 / 0 Регистрация: 04.11.2014 Сообщений: 11
	26.03.2015, 17:12 [ТС]	14
	Все элементы массива различны-думаю, это надо как-то учитывать. С тернарником непонятно-этот элемент может быть "пропастью", например на массиве {1 2 5 7 9 1 10}, при индексации с 0, мы возьмем элементы на 2 и 4 позиции, т.е. 5 и 7, и пойдет троичный поиск от 0 до 4. Массив не является перестановкой, просто все элементы различны 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,471
	26.03.2015, 18:12	15
	1) по-моему, не решается Возьмём отсортированный массив и добавим в него число Х на произвольную позицию. Как теперь найти X за O(logn)? По-моему, никак. Чтобы найти X придётся проверить все элементы массива. Тот факт, что до добавления Х массив был отсортирован, нам никак не помогает. А получившийся новый массив можно рассматривать как два отсортированных массива из условия задачи. Х будет либо последним элементом первого отсортированного массива, ли первым элементом второго. 0