Kohila G Ответов: 2

Какое решение вы считаете наиболее эффективным? И как это сказать?


Код приведен на сайте.
Наименьший элемент повторяется ровно ‘k’ раз (не ограничиваясь малым диапазоном) - GeeksforGeeks[^]
Какой код является наиболее эффективным из этих двух?
Кстати, оба показывают правильный вывод.

Что я уже пробовал:

/*https://www.geeksforgeeks.org/smallest-element-repeated-exactly-k-times-not-limited-small-range/
Smallest element repeated exactly ‘k’ times (not limited to small range)
*/
#include<bits/stdc++.h>
using namespace std;
int no_of_chars = 10;
int smallrepeat(int s[],int k, int n)
{
	int hash[no_of_chars] = {0};
	//Storing the frequency of occurances.
	for(int i=0;i<n;i++)
		hash[s[i]]++;
	//Finding smallest element repeated exactly 'k' times
	int repeatmore = 9;
	for(int i=0;i<n;i++){
		if(hash[s[i]] && (hash[s[i]] == k) && (s[i] < repeatmore))
			repeatmore = s[i];
	}

	return repeatmore;

}
int main()
{
	int s[] = { 2, 2, 1, 3, 1 };
	int n = sizeof(s)/sizeof(s[0]);
	int k = 2;
	cout<<"Smallest element repeated exactly ‘k’ times :"<<smallrepeat(s,k,n)<<endl;
}

Richard MacCutchan

Вероятно, ни то, ни другое, поскольку образцы слишком малы. Настройте некоторые временные тесты с большими выборками, и вы легко найдете ответ.

Kohila G

Итак, решение, которое занимает меньше времени, является наиболее эффективным? Оба они имеют одинаковую временную сложность : O(n).

Dave Kreskowiak

Необязательно. Время-не единственная мера "эффективности". Что определяет эффективность, так это обстоятельства, при которых код должен быть запущен, чтобы быть "эффективным". Будет ли требование к коду-это время? Будет ли это использование памяти? Будет ли это влиять на загрузку процессора? Зависит ли это от ввода-вывода? Совместное использование ресурсов? ...

2 Ответов

Рейтинг:
2

Rick York

Версия веб-сайта, скорее всего, будет быстрее из двух, но только с очень, очень небольшим отрывом, потому что у нее на одно сравнение меньше в своем цикле. У вашего есть дополнительная проверка на нулевое значение хэш-массива, которая кажется ненужной. Без этой проверки у обоих была бы почти одинаковая производительность. Разница, вероятно, будет неизмеримой, если вы не используете очень большой массив данных и не тестируете несколько циклов, например 100K или более.

В режиме выпуска тонкие различия в коде будут в основном оптимизированы компилятором. Это будут части .begin() и .end() цикла for и вызов min, который обычно встроен.


Рейтинг:
2

CPallini

Они в основном одинаковы. Обратите внимание, что ваша программа не производит тот же вывод, что и на веб-стороне, если элемент не найден.