Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
masogg
0 / 0 / 0
Регистрация: 19.04.2013
Сообщений: 5
#1

Определить сложность алгоритма - C++

21.11.2015, 20:21. Просмотров 261. Ответов 1
Метки нет (Все метки)

Помогите , пожалуйста, выполнить задания. Буду благодарен за объяснение , так как не понимаю как это делать.

Какое значение возвращает следующая функция? Ответ должен быть в форме функции числа n. Найдите время исполнения в наихудшем случае , используя обозначение О-большое.

на входе метода аргумент int n;
C++
1
2
3
4
5
6
int r = 0;
for(int i = 0; i < n - 1; i++)
  for(int j = i + 1; j < n; j++)
    for(int k = 0; k < j; k++)
      r++;
return r;
как я предполагаю сложность будет n^3 ,а ответ n^2(n-1) ?

второе задание.
Докажите, что если f1(n)=O(g1(n)) и f2(n)=O(g2(n)), тогда f1(n)*f2(n)=O(g1(n)*g2(n))

Буду Вам очень благодарен за любую помощь!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.11.2015, 20:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Определить сложность алгоритма (C++):

Определить сложность алгоритма - C++
Ребята подскажите сложность алгоритма:) Функция ищет максимальный элемент в двухмерном массиве. Это будет n*m или n^2? int*...

Определить сложность алгоритма - C++
для i от 1 до n нц s = 0; для j от 1 до n нц s = s + a * x; кц ...

Временная сложность алгоритма - C++
Помогите посчитать временную сложность след. алгоритма. Желательно с объяснениями, а не просто результат. #include &lt;iostream&gt; #include...

Временная сложность алгоритма - C++
Всем привет! Пусть есть натуральные числа а и n. Найти a в степени n. Временная сложность алгоритма должна быть О(log2n)

Нужно посчитать сложность алгоритма - C++
Дорогие обитатели форума, нужно посчитать сложность рекурсивной функции удаления вершин из бинарного дерева. К сожалению, не представляю,...

Как рассчитать сложность алгоритма? - C++
Помогите мне пожалуйста Я не понимаю много о сложности алгоритма. Как рассчитывать сложность алгоритма в этом коде? #include...

1
Dimension
Dimension
569 / 438 / 135
Регистрация: 08.04.2014
Сообщений: 1,709
Завершенные тесты: 1
21.11.2015, 20:46 #2
первый цикл дает n-1 , второй 2n , третий 6n , всего (n-1)*(2n)*(6n)=12n2*(n-1),при больших числах 12 можно отбросить
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.11.2015, 20:46
Привет! Вот еще темы с ответами:

Как узнать сложность алгоритма(ресурсы ,способы) - C++
Здравствуйте, нужно узнать сложность какой-нибудь ф-ии из стандартной библиотеки cpp. Где это можно узнать? Например max_element(it it)...

Какова временная сложность метода ветвей и границ, и генетического алгоритма, которые решают задачу о рюкзаке? - C++
Всем привет!Не подскажете какова временная сложность метода ветвей и границ,и генетического алгоритма,которые решают задачу о рюкзаке? и...

Определить сетку разбиения для нечеткой модели на основе алгоритма кластеризации Густавсона-Кесселя - C++
Помогите пожалуйста с заданием: Нужно определить сетку разбиения для нечеткой модели на основе алгоритма кластеризации Густавсона-Кесселя

Небольшая сложность - C++
Я создал проект, сохранил, попытался открыть, но на месте отладки появилось &quot;присоединить&quot;, при нажатии которого выдаёт окошко с кучей...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru