Как найти эффективности (большой обозначение O) в поиске общей сложности каждой строки из 2D-массива
Эффективность кода
void findTotal(int arr[3][],int rows,int cols)
{
int *total=new int[rows];
int sum;
for(int r=0;r<rows;r++)
{
sum=0;
for(int c=0;c<cols;c++)
sum=sum+arr[r][c];
total[r]=sum;
}
for(int k=0;k<rows;k++)
cout<<total[k]<<endl;
delete []total;
}
Добро пожаловать ТАК!
Надеюсь, что это объяснение немного облегчит ситуацию.
Эффективность в основном может быть определена как
«Рост функций с точки зрения ввода размера п.»
Нотация Big O позволяет классифицировать алгоритмы как реагировать (с точки зрения времени или пространства) на изменения размера ввода.
В вашем случае ваш вход представляет собой 2D-массив, который имеет несколько строк и несколько столбцов. Ваш цикл for проходит через каждую строку, а вложенный - через каждый столбец каждой строки в вашем 2D-массиве. Н2СО3 этого права, Большие О этой функции O(rows*columns)
Других примеров различной эффективности являются:
О (п) - линейно - растет с той же скоростью, что и размером входного; пример - поиск предмета в несортированном массиве
O (1) - постоянный - не растет - остается неизменным; пример - хеш-таблицы.
O (log n) - логарифмический; пример: двоичный поиск
O (n log n) - linearithmic; пример: слияние сортировки, quicksort и т. д.
Для получения дополнительной информации вы всегда должны задать свой вопрос Google.
В Википедии также есть список замечательных статей об информатике, таких как Big O Notation и так далее.
Вы можете найти его, изучив теоретическую информатику. –
О, и прежде, чем вы спросите: «Я знаю, но какой результат», это «O (rows * cols)». –
@ H2CO3 Нет, это 'O (cols)'. Если 'rows> 3', вы можете получить segfault после 4 итераций. – amit