Помогите посчитать количество операций в алгоритме
Yerke
Помогите посчитать количество операций в алгоритме
Добрый день,
Имеется код, который определяет первое число, встречающееся ровно 3 раза в массиве. Требуется определить количество операций, выполняемых кодом, в лучшем и худшем случаях, то есть необходимо определить точную сложность алгоритма. Я предполагаю, что общая сложность кода равна О (n), но мне нужно записать ответ в виде, например, 3n + 5. По моим подсчетам, в лучшем случае сложность равна 14 = О (1), в худшем случае 5n = О (n). Подскажите, пожалуйста, правильны ли мои подсчеты? Рядом с каждой строчкой я написала количество операций (best case - лучший случай, worst case - худший случай). Для примера, for(int i = 0; i < a.length; i++) - это 2(n + 1) операций, где n - количество элементов в массиве. И еще, вначале я ищу максимальное значение в массиве (max) и создаю новый массив с max + 1 элементами, в который записываю частоту чисел и индекс, где встречается это число, так как мне нужно определить первое число, встречающееся 3 раза. Потом я ищу число с частотой 3 и с минимальным индексом в третьем цикле, но здесь я не уверена, будет ли О (n) или нет. И каждое сравнение типа min == 1 в if тоже считается. Заранее спасибо.
Ответы:
Иван Сигаев
"Имеется код, который определяет первое число, встречающееся ровно 3 раза в массиве"
А код ниже вообще непонятно что делает
типовое решение цикл по элементам и вложенный цикл по оставшимся элементам со счетчиком совпадений
примерно так
for(i=0;i<a.length-2;i++){
cnt=1;for(j=i+1;j<a.length;j++)
if(a[i]==a[j])cnt++;
if(cnt==3)return a[i];
}
Валерий Шестаков
Откуда взялось "По моим подсчетам, в лучшем случае сложность равна 14 = О (1)", если во второй строчке уже 2(n+1) = O(n) без всяких условий?
|