ДК
int val;
scanf(“%d”, &val);
//for цикл
array[i] += 10/ val;
Он каждый раз делит 10 на val
/O2 включено
scanf(“%d”, &val);
//for цикл
array[i] += 10/ val;
Он каждый раз делит 10 на val
/O2 включено
Size: a a a
2020 September 04
НП
Как понять решение сложности O(n2)?
ДК
Как понять решение сложности O(n2)?
Условно у нас есть массив длиной n.
И нам нужно его отсортировать.
Для сортировки нужно несколько проходов. Вот, n^2 отображает, что максимальное количество элементов, которое нам нужно будет пробежать по массиву - n^2
И нам нужно его отсортировать.
Для сортировки нужно несколько проходов. Вот, n^2 отображает, что максимальное количество элементов, которое нам нужно будет пробежать по массиву - n^2
ДК
ДК
У нас есть массив длинной n
Нам нужно его распечатать.
Обращение к элементу в массиве занимает O(1) - т.е. требуется 1 операция
Нам нужно его распечатать.
Обращение к элементу в массиве занимает O(1) - т.е. требуется 1 операция
ДК
У нас есть массив длинной n
Нам нужно его распечатать.
Обращение к элементу в массиве занимает O(1) - т.е. требуется 1 операция
Нам нужно его распечатать.
Обращение к элементу в массиве занимает O(1) - т.е. требуется 1 операция
Следовательно чтобы распечатать массив, нам нужно обратится к каждому элементу, следовательно, получаем время требуемое на получение всего массива O(n)
ДК
Возможно плохо объяснил, но все же
НП
Условно у нас есть массив длиной n.
И нам нужно его отсортировать.
Для сортировки нужно несколько проходов. Вот, n^2 отображает, что максимальное количество элементов, которое нам нужно будет пробежать по массиву - n^2
И нам нужно его отсортировать.
Для сортировки нужно несколько проходов. Вот, n^2 отображает, что максимальное количество элементов, которое нам нужно будет пробежать по массиву - n^2
тогда бы написали O(n**2)
OM
наверное в оригинале было n² потом текст потерял какие-то свойства и осталсь n2
ДК
тогда бы написали O(n**2)
А, я думал вам нужно объяснить что значит O() в целом
НП
А, я думал вам нужно объяснить что значит O() в целом
Не, я перед этим погуглил тему
m
Как понять решение сложности O(n2)?
В И К И П Е Д И Я
И
К
И
П
Е
Д
И
ЯНП
В И К И П Е Д И Я
И
К
И
П
Е
Д
И
Яуууу, её я открыл по первой ссылке. Составлял её какой то урод.
НП
m
m
у меня же был курс матана
m
что тут непонятного
НП
Да всё не понятно. Там три потому что три было изначально или там три потому что тройка в степени и тройка во второй половине произвели какое то колдунство и родили еще одну тройку. Кароче туманный пример.
OM
какой курс? в матанализе есть примерно такое же нотация Ландау. О-большое.
КК
Да всё не понятно. Там три потому что три было изначально или там три потому что тройка в степени и тройка во второй половине произвели какое то колдунство и родили еще одну тройку. Кароче туманный пример.
просто степень многочлена