Верно ли равенство (x + y)^2 = О(x^2 + y^2)?

Question

[ResearcherV]

Верно ли это равенство, и как доказывается?

Answer 1

[dollar]

Не верно. Очевидно. Потому что 2xy = O(1)
Верно.
Пусть C = 3
Докажем, что (x + y)^2 <= 3 * (x^2 + y^2) при x > 0 и y > 0:
после преобразований 2*x*y <= 2*x^2 + 2*y^2
Если x < y, то 2*x*y < 2*y^2
Если x >= y, то 2*x*y <= 2*x^2
ч.т.д.

Comments

[Андрей]

А если x == y && x == 0?=)

[dollar]

Андрей, в каком смысле?

[longclaps]

dollar, да верно оно.

[dollar]

longclaps, Андрей, там О большое в вопросе.

[ResearcherV]

А ход мыслей можно немного разъяснить? Автор книги имеет другое мнение.

[longclaps]

dollar, ну так О(t) <= {некотарая константа} * t
Здесь:

if 0 < x < y:
    (x + y)^2 < 4 * y^2 < 4 * (x^2 + y^2)

и т.д.

[dollar]

longclaps,
Может я чего-то не знаю?
f = O(g) означает, что f растёт не быстрее, чем g

[ResearcherV]

longclaps, почему множитель именно 4?

[dollar]

В общем, уравнение сводится к
2xy = O(1), что, очевидно, не верно.
И, кстати, это не уравнение, а запись такая. Знак равенства чисто условный.

[longclaps]

Я доказал для конкретного случая 0 < x < y
Потому что x + y < y + y < 2 * y

Кстати, а с чего ты назвался ResearcherV? Назови себя Voproshacher.

[ResearcherV]

longclaps, хорошая идея, спасибо за совет.

[ResearcherV]

longclaps, Кстати, y + y не меньше 2*y

[longclaps]

dollar, да в вики же

фраза «сложность алгоритма есть O(f(n))» означает, что с увеличением параметра n, характеризующего количество входной информации алгоритма, время работы алгоритма будет возрастать не быстрее, чем некоторая константа, умноженная на f(n);

[longclaps]

ResearcherV, вот, ты уже зашевелился самостоятельно )

[dollar]

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

[longclaps]

dollar, ну вот я тебе подкинул константу 4.

[dollar]

longclaps, да, ты прав

[dollar]

Достаточно константы 3.

[Андрей]

dollar, если x=0 и y=0 - О не имеет никакого значения)) д

Answer 2

[aleks-th]

Ну если x=0 и y = 0
Верно однозначно )
--

При других значениях лень смотреть.... да и непонятно там O(....) или 0(.....) ?

Comments

[ResearcherV]

Именно О. Не 0