Нахождение наибольшего значения в массиве и эффективность кода

Question

Я хочу знать, верна ли моя концепция и понимание кода! Здесь я сначала устанавливаю последнее число как максимальное, а затем использую другое для l oop, чтобы сравнить каждое значение со всеми другими значениями, чтобы найти наибольшее значение, верно? Также время выполнения этого - O (n ^ 2), поскольку здесь используется два для l oop? Я знаю, что существует лучшее линейное решение (O (n)), но я хочу вручную увидеть и проверить, сколько времени потребуется на его выполнение, а также попытаться сравнить эффективность между двумя. Я также не знаю, какова пространственная сложность этого кода. Будем очень признательны за любые дальнейшие объяснения.

 /*The following code will return the largest value in an array of non-negative integers */
int CompareToAll (int array[], int n)
{
    int i, j;
    bool isMax;

    if (n <= 0)
       return -1;

    for (i = n-1; i > 0; i--) {
         isMax = true;
         for (j = 0; j < n; j++) {
            if (array[j] > array[i]) {
               isMax = false;
               break;
            }
         }
            if (isMax) break;
         }

         return array[i];
    }

Answer 1

Да, pessimisti c сложность этого алгоритма O(n^2), optimisti c is O(n).

Optimisti c

Первый / последний элемент - самый большой . В этом случае будет выполнен только один проход (либо l oop), поэтому каждый элемент будет посещен только один раз.

Pessimisti c

Средний элемент является самым большим. В таком случае внешний l oop будет выполняться n/2 раз, а внутренний l oop n/2 раз, пока половина массива не будет достигнута внешним l oop.

Это дает нам 1/2 * n * 1/2 * n, что равно O(n^2), поскольку константа не имеет значения.

Это также ваше среднее значение, поскольку у нас нет никаких предположений относительно ваших данных, которые будут использоваться здесь.

Решение O (n)

Go с любого конца массива и сохраните максимальное видимое значение и переключитесь, если будет найдено большее значение. Вернуть самый большой после посещения всех элементов.

Answer 2

Поскольку вы используете массив, обозначение пространственной сложности будет эквивалентно временной сложности. Следовательно, в вашем случае сложность пространства будет O (n ^ 2).

Алгоритм O (n) будет наряду с его сравнением для длины массива до 1000000 в наносекундах: Однако время кажется не работает правильно, так как он слишком сильно меняется. Но да, должно быть что-то вроде этого.

Время, затраченное с размером массива 10 Алгоритм O (n) 0 наносекунд, алгоритм O (n ^ 2) 0 наносекунд

Время, затраченное при размере массива 100 Алгоритм O (n) 0 микросекунд Алгоритм O (n ^ 2) 0 микросекунд

Время, затраченное на размер массива 1000 Алгоритм O (n) 4 микросекунды Алгоритм O (n ^ 2) 5 микросекунд

Время, затраченное на размер массива 10000 Алгоритм O (n) 39 микросекунд Алгоритм O (n ^ 2) 48 микросекунд

Время, затраченное на размер массива 100000 Алгоритм O (n) 2293 микросекунды Алгоритм O (n ^ 2) 4189 микросекунд

Время, затраченное на размер массива 1000000 Алгоритм O (n) 3271 микросекунда Алгоритм O (n ^ 2) 9715 микросекунд

    #include <algorithm> 
    #include <chrono> 
    #include <iostream> 
    using namespace std; 
    using namespace std::chrono; 

    // O(n)
    int findMax(int arr[], int n){

        int maxindex = -1; // to return the position of the maximum value 
        int maxvalue = -1; // // negative hence smallest number amongst positive integers 
        for(int i=0 ; i< n ; i++ ){
    if(arr[i] > maxvalue) {
        maxvalue = arr[i]; // storing max value for next comparison 
        maxindex = i ; //stopring max index to return 
    }
} 
        if( maxindex<0 ) return -1; //list full of negative values 
        return arr[maxindex];

    }

    // O(n^2)
    int CompareToAll(int array[], int n) // your algorithm 
    {
int i, j;
bool isMax;
if (n <= 0)
   return -1;
for (i = n-1; i > 0; i--) {
     isMax = true;
     for (j = 0; j < n; j++) {
        if (array[j] > array[i]) {
           isMax = false;
           break;
        }
     }
             if (isMax) break;
        }

        return array[i];
    }





    int main()
    {
for (int i=10 ; i<=1000000; i=i*10){
int arr[i];

for(int j =0 ; j<i ; j++ ){
    arr[j] = j*2 ; 
}
cout<< endl << "Time taken with array size " << i; 
// Get starting timepoint 
auto start_n = high_resolution_clock::now(); 
findMax(arr,i); 
auto end_n = high_resolution_clock::now();
cout<<endl;
auto duration = duration_cast<microseconds>(end_n - start_n); 
cout<<"O(n) algorithm " <<duration.count() << " nanoseconds"<<endl;


// Get starting timepoint 
auto start = high_resolution_clock::now(); 
CompareToAll(arr,i);
auto end = high_resolution_clock::now();
auto duration2 = duration_cast<microseconds>(end - start); 
cout<< "O(n^2) algorithm " << duration2.count()<< " nanoseconds";
cout<<endl; 
cout<< "------------------";
};
return 0;
    }

Answer 3

Временная сложность составляет O(n^2) в среднем и худшем случае.

Обратите внимание, что этот al go имеет лучший случай со сложностью O(n) (когда `` isMax находится на первом итерация (и)).

Сложность пространства равна O(1) - вы используете только постоянное пространство вне зависимости от размера массива