for (int j=0,k=0; j<n; j++)
for (double m=1; m<n; m*=2)
k++;
Я думаю, что это O (n^2), но я не уверен. Я работаю над проблемой практики и у меня есть следующие варианты:Big O этого уравнения?
Его O (Nlog п). Блок кода запускает n * log n раз.
Предполагается, что n=16; Затем первый цикл запускает 16 (= n) раз. А вторая петля работает 4 (= log n) раз (m = 1,2,4,8). Таким образом, внутренний оператор k++ работает 64 раза = (n * log n) раз.
Хммм ... хорошо, сломайте его.
Кажется очевидным, что внешний контур равен O (n). Он увеличивается на 1 каждую итерацию. Внутренний цикл, однако, увеличивается на мощность 2. Экспоненты, безусловно, связаны (фактически наоборот) с логарифмами.
Почему вы пришли к решению O (n^2)? Докажите это.
У меня нет доказательств. Я знаю, что это не п! хотя это может быть справедливо для маленьких n. n^2 казался логичным, так как сложность большого вывода никогда не интерпретируется полностью точно, и поскольку вложены петли с внешним циклом из n итераций и внутренний цикл меньших итераций. Я предполагаю, что мой первоначальный ответ был правдой. – snotyak
Хорошо. Теперь мы куда-то добираемся. Предоставление вышеуказанного комментария в вашем первоначальном вопросе обеспечило бы более полное представление о том, о чем вы думали. Устранение n! например. – sberry
Я просто переживал проблемы с практикой, думая, что это намного сложнее, чем на самом деле. Из-за вас и Шиплу я работал сам по себе с различными тестовыми значениями (1, 5, 8, 16, 32, 64). Нет никакой реальной причины, чтобы число было неточным, так как log (n) уничтожает то, что эффективно 2^m. Спасибо, я должен попробовать еще раз в следующий раз. – snotyak
Общий подход к решению подобных задач состоит в том, чтобы рассмотреть порядок каждого цикла, и поскольку они вложены, вы можете умножить обозначения «O».
Некоторые простые правила для большого "О":
O(n)O(m) = O(nm)O(n) + O(m) = O(n + m)O(kn) = O(n) где 'к' некоторые постоянныеВ итерации цикла 'J' через п элементов , так ясно, что это O (n). Цикл «m» выполняет итерацию по элементам log (n), поэтому это O (log (n)).
Поскольку петли вложены, наш конечный результат будет O(n) * O(log(n)) = O(n*log(n)).
позволяет взглянуть на наихудшее поведение. для поиска второго цикла продолжается от 1, 2, 4, 8 .... скажем, что n равно 2^k для некоторого k> = 0. В худшем случае мы могли бы найти до 2^k и понять, что мы преодолели цель. Теперь мы знаем, что цель может быть в 2^(k - 1) и 2^k. Число элементов в этом диапазоне составляет 2^(k - 1) (подумайте секунду). Число элементов, которые мы рассмотрели до сих пор, равно O (k), которое равно O (logn), а для первого цикла это O (n). (Слишком просто для выяснения). то порядок всего кода будет O (n (logn)).
Кроме того, что проблема неправильная, вопрос помечен домашней работой, поэтому вы должны давать подсказки и объяснения, а не просто результат. –
@JanHudec Я не знал соглашений о * домашнем задании *. Пояснение добавлено. Благодарю. –
Вы также должны быть осторожны, чтобы не дать неправильный ответ, как это было до вашего редактирования. – sberry