@jvmchat
ThisIs25.03.2016
10:12:13
10:12:13
почему?
Igor25.03.2016
10:12:29
10:12:29
другой провайдер, другая страна)
GoogleThisIs25.03.2016
10:12:39
10:12:39
из России кто нибудь попробуйте зайти в гитхаб
Виталий25.03.2016
10:12:55
10:12:55
заходит
ThisIs25.03.2016
10:13:22
10:13:22
ясно спасибо)
[Anonymous]25.03.2016
11:56:09
11:56:09
в данном случае имеют в виду, что размер используемой памяти постоянная величина, ты не можешь выделять её
Andre25.03.2016
11:58:52
11:58:52
Ну так в таком случае свапаешь местами и все
Maksim25.03.2016
11:59:13
11:59:13
Свап будет за O(n^2).
Konstantin25.03.2016
12:00:22
12:00:22
[Anonymous]25.03.2016
12:00:34
12:00:34
>используя O(n) времени
другими словами, тебе можно пройтись по списку только один раз
и за этот один раз сразу разворачивать его
Maksim25.03.2016
12:02:41
12:02:41
Разве есть ограничение на один раз? Хоть тысячу, главное, чтобы не было зависимости по размеру данных)
Igor25.03.2016
12:02:54
12:02:54
O(n) на выполнение ведь
Google
Andrey25.03.2016
12:03:20
12:03:20
Эм, а в чём проблема с O(1) памяти?
Igor25.03.2016
12:03:22
12:03:22
там стремный алгоритм, погугли
Andrey25.03.2016
12:03:33
12:03:33
Типа такого будет `
[Anonymous]25.03.2016
12:03:50
12:03:50
n - количество элементов, предполагается, что на каждый элемент тратится единица времени
Igor25.03.2016
12:04:26
12:04:26
ну можно проходить конечное число раз, не зависящее от n
только это не особо поможет
Pavel ?25.03.2016
12:05:28
12:05:28
)))
что значит развернуть в O(n) и по памяти O(1)? O(n) он в любом случае разворачивается, а что есть O(1) памяти?)
хотя
Igor25.03.2016
12:08:24
12:08:24
можно создать пару переменных, которые не будут зависеть от n - это про память
Andrey25.03.2016
12:08:26
12:08:26
Вот же решение:
Pavel ?25.03.2016
12:08:48
12:08:48
тут вот че
Andrey25.03.2016
12:08:55
12:08:55
Только в конце не x->end(), а null.
[Anonymous]25.03.2016
12:09:12
12:09:12
что значит развернуть в O(n) и по памяти O(1)? O(n) он в любом случае разворачивается, а что есть O(1) памяти?)
Это значит, что нужно развернуть список за один проход по нему без выделения памятиAndrey25.03.2016
12:09:44
12:09:44
Это значит, что нужно развернуть список за один проход по нему без выделения памяти
Нет, O(1) - это значит, что количество используемой памяти не зависит от количества элементов в списке.Andrey25.03.2016
12:12:35
12:12:35
Только за верный синтаксис не ручаюсь, писал больше на псевдокоде.
GooglePavel ?25.03.2016
12:13:20
12:13:20
тут нет доступа O(1)
Pavel ?25.03.2016
12:14:19
12:14:19
трудно сказать) но видимо им нужен массив с индексом)
[Anonymous]25.03.2016
12:14:43
12:14:43
Нет, O(1) - это значит, что количество используемой памяти не зависит от количества элементов в списке.
нет не не зависит, размер памяти - константапоэтому там единица стоит
Виталий25.03.2016
12:15:03
12:15:03
Andrey25.03.2016
12:15:13
12:15:13
[Anonymous]25.03.2016
12:16:23
12:16:23
ты написал, что размер памяти просто не зависит, а значит может менять свое значение внезависимости от списка
но это неверно
потому что О(1) говорит, что изменять размер данной памяти нельзя
Igor25.03.2016
12:17:11
12:17:11
ну выделить память на 10 элементов, к примеру, можно
если 10 хватит для всех случаев
или нет?
[Anonymous]25.03.2016
12:19:27
12:19:27
нет
Igor25.03.2016
12:19:58
12:19:58
T(n) = O(f(n)) <=> T(n) <= c*f(n) для любого n >= n0
[Anonymous]25.03.2016
12:20:09
12:20:09
выделять память нельзя совсем
Google[Anonymous]25.03.2016
12:20:53
12:20:53
О(1)
Igor25.03.2016
12:21:17
12:21:17
и не возвращайся, пока не дочитаешь)
Andrey25.03.2016
12:21:36
12:21:36
Igor25.03.2016
12:22:39
12:22:39
ну выделить память на 10 элементов, к примеру, можно
Andrey25.03.2016
12:23:11
12:23:11
расскажешь это в яндексе в-общем
Эм, Т.е. вы считаете, что "О(1) дополнительной памяти" - это нельзя память выделять?[Anonymous]25.03.2016
12:23:13
12:23:13
оно может быть хоть 2043434354564535454
смысл в самом факте что там число
а не n
потому что n означает переменное значение, зависящее от размера данных
GoogleAndrey25.03.2016
12:24:00
12:24:00
потому что n означает переменное значение, зависящее от размера данных
Так, ты что подразумеваешь под выделением памяти?Здесь я память выделял?
Igor25.03.2016
12:24:54
12:24:54
то ли ты херню пишешь, то ли мы одно и то же разными словами говорим
[Anonymous]25.03.2016
12:25:27
12:25:27
верно третье: вы никогда не решали олимпиадные задачи по программированию
и поэтому слышали про эту натацию лишь краем уха
Igor25.03.2016
12:25:37
12:25:37
при O(1) выделить константное количество памяти можно
Andrey25.03.2016
12:25:59
12:25:59
Igor25.03.2016
12:26:00
12:26:00
ога, курс алгоритмов я тоже краем уха слушал
[Anonymous]25.03.2016
12:26:21
12:26:21
оно уже выделено - на входной список
Andrey25.03.2016
12:26:42
12:26:42
верно третье: вы никогда не решали олимпиадные задачи по программированию
Тебе на алгоритм дали О(n) времени и О(1) памяти. Что не так в наших рассуждениях?Andrey25.03.2016
12:26:56
12:26:56
И не важно есть ли слово "дополнительной" или нет.
Открыть в Telegram