Допустим есть такой код
for(int i = 0; i < 10; i++)
for(int i = 0; i < 10; i++)
if(...)
{} else {}
Тут сложность будет i * j
или if
добавит сложность и будет что-то в духе i*j * 2
к примеру?
Stack Overflow на русском — это сайт вопросов и ответов для программистов. Присоединяйтесь! Регистрация займёт не больше минуты.
Присоединиться к сообществуДопустим есть такой код
for(int i = 0; i < 10; i++)
for(int i = 0; i < 10; i++)
if(...)
{} else {}
Тут сложность будет i * j
или if
добавит сложность и будет что-то в духе i*j * 2
к примеру?
смотри, итоговая сложность будет зависеть от того, что происходит внутри if
Сложность i * j набирается только из двух циклов.
Общая сложность будет произведением i * j * (сложность того, что в if)
if (i == j)
, что сразу понижает сложность. Для оценки сложности нужен полный алгоритм и детальное исследование.
– KoVadim
11 мар '13 в 21:24
do_some_action
средней сложности функция? O(n^2) ( это Ваш i*j
) или O(n).
– KoVadim
11 мар '13 в 21:55
O(1)
. – VladD 11 мар '13 в 21:53