Как оптимизировать этот алгоритм до O(n)?

@stympel · Регистрация: 17.05.2017

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

У меня есть список m и число n. Нужно найти два элемента из этого списка, сумма которых будет ближе всего к n. Как это можно сделать за O(n)?

@TimeTwo · 08.11.2018, 17:04

O(n) означает, что вам нужно решить эту задачу используя лишь один цикл

@stympel · 08.11.2018, 17:37 **[ТС]**

Я знаю, я спросил как сделать так, чтобы сложность алгоритма была O(n).

@TimeTwo · 08.11.2018, 19:11

для начала, можно сделать как нибудь не привязываясь к сложности алгоритма, осознать задачу и потом оптимизировать

Вы бы могли написать так:

есть список m и число n. Нужно найти два элемента из этого списка, сумма которых будет ближе всего к n

вам возможно кто нибудь бы помог, и из этого, осознав алгоримт, вы бы могли придумать оптимизированный

вообще в вашей задаче слишком много нюансов:

сумма будет ближе всего к n, но при этом не больше и не равна?
можно ли использовать сложность 2n или 3n, ведь когда n стремиться к бесконечности 2 и 3 не играют никакой роли...

@stympel · 08.11.2018, 20:32 **[ТС]**

Вы правы, сейчас сделаю новый вопрос с более понятным названием. Может быть равно, если нет таких чисел, то максимально приближенные два числа, сумма которых и будет равняться n.

@TimeTwo · 09.11.2018, 12:34

сложность данного алгоритма 2n, так же можно при сумме равно n делать break из цикла

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import random
a = [random.randint(1, x) for x in range(1, random.randint(1,100))]
print(a)
 
n = random.randint(1,50)
memory1 = 0
memory2 = min(a)
 
for obj in a:
    if obj > memory1 and obj+memory2 <= n:
        memory1 = obj
    if obj > memory2 and obj+memory1 <= n:
        memory2 = obj
 
print('n = {} \n memory1 = {} \n memory2 = {}'.format(n, memory1, memory2))

@stympel · 09.11.2018, 16:14 **[ТС]**

Большое спасибо!
Так же есть алгоритм, который делает все за O(n), если интересно, то могу показать.

Новые блоги и статьи Все статьи Все блоги /
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
Реалии Hrethgir 01.03.2026 Нет, я не закончил до сих пор симулятор. Эта задача сложнее. Не получилось уйти в плавсостав, но оно и к лучшему, возможно. Точнее получалось - но сварщиком в палубную команду, а это значит, в моём. . .	Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек: SDL3, Box2D, FreeType, SDL3_ttf, SDL3_mixer и SDL3_image из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual Studio. . . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .

@stympel 1 / 1 / 1 Регистрация: 17.05.2017 Сообщений: 97

	Как оптимизировать этот алгоритм до O(n)? 08.11.2018, 14:51. Показов 1117. Ответов 6 Метки алгоритмы (Все метки) У меня есть список m и число n. Нужно найти два элемента из этого списка, сумма которых будет ближе всего к n. Как это можно сделать за O(n)? 0

@TimeTwo 102 / 95 / 104 Регистрация: 29.11.2009 Сообщений: 407
	08.11.2018, 17:04
	O(n) означает, что вам нужно решить эту задачу используя лишь один цикл 0

@stympel 1 / 1 / 1 Регистрация: 17.05.2017 Сообщений: 97
	08.11.2018, 17:37 [ТС]
	Я знаю, я спросил как сделать так, чтобы сложность алгоритма была O(n). 0

@stympel 1 / 1 / 1 Регистрация: 17.05.2017 Сообщений: 97
	08.11.2018, 20:32 [ТС]
	Вы правы, сейчас сделаю новый вопрос с более понятным названием. Может быть равно, если нет таких чисел, то максимально приближенные два числа, сумма которых и будет равняться n. 0

@stympel 1 / 1 / 1 Регистрация: 17.05.2017 Сообщений: 97
	09.11.2018, 16:14 [ТС]
	Большое спасибо! Так же есть алгоритм, который делает все за O(n), если интересно, то могу показать. 0