Какова временная сложность следующего кода и как его изменить на линейную или логарифмическую временную сложность?

Question

long int num,max,mod,a,i,j; 
cin>>num; 
long int arr[num]; 
for(a=0;a<num;a++) 
{ 
    cin>>arr[a]; 
} 
max=arr[0]%arr[0]; 
for(i=0;i<num;i++) 
{ 
    for(j=0;j<num;j++) 
    { 
     mod=arr[i]%arr[j]; 
     if(mod>max) 
     { 
      max=mod; 
     } 
    } 
} 
cout<<max; 

Я предполагаю, что это o (n^n), если нет, то сообщите временную сложность и как?
И, во-вторых, код над кодом может быть преобразован в линейную или логарифмическую временную сложность. Я новичок в области Data-Structures and algorithms, пожалуйста, помогите мне решить эту проблему.
Будет здорово, если вы предоставите код. Спасибо :)

Answer 1

Я не понимаю, почему люди голосуют за этот вопрос. Это довольно интересно.

Если все входы являются положительными числами, нужный результат на самом деле является вторым максимальным значением. Я считаю, что вы можете сами его закодировать. Доказательство состоит в том, что результат должен быть числом mod максимального числа, а второе максимальное число mod наибольшее даст оптимальный результат и эквивалентно второму по величине числу. Но будьте осторожны, если имеется более одного максимального числа, вам нужно проверить следующий по величине.

Если некоторые цифры отрицательные, это может быть немного сложнее. Я предполагаю, что результат модуля всегда положителен. (Хотя в C это не работает, но вы можете просто игнорировать эти отрицательные числа в этом случае). Сначала нам нужна копия массива, а все отрицательные числа преобразуются в положительные. Во-вторых, нам нужны три числа из двух массивов, второй максимум положительный и наибольшее отрицательное число (ближайший к 0) от исходного массива и наибольшее число из второго массива (все преобразованы в положительные). Сравните оба первых числа по третьему числу, выведите более крупный.

Answer 2

Я сделал ваш оригинальный код работающим, чтобы у вас была начальная точка.

template <class T> 
T maxmod(vector<T> const& arr) 
{ 
    auto max = numeric_limits<T>::lowest(); 
    for(auto x : arr) 
     for (auto y : arr) 
     max = std::max(max, y ? x%y : 0); 
    return max; 
} 

Ваша проблема заключается в том, достаточно интересно и зависит от знака условностями операции по модулю (которая была определена реализация до C++ 03). Как правило, это должно быть возможно разрешено в линейном времени, комбинируя максимальные поиски с некоторыми преобразованиями. Вот первая линейная попытка

template <class T> 
T my_maxmod(vector<T> arr) // deep copy array because we change it 
{ 
    T max = *std::max_element(arr.cbegin(), arr.cend()); // O(N) 
    assert(max != 0); // TODO 
    std::transform(arr.begin(), arr.end(), arr.begin(), [max](T const& a){ // O(N) 
     return a % max; 
    }); 
    max = *std::max_element(arr.cbegin(), arr.cend()); // O(N) 
    return max; 
} 

Это не работает для всех входов. И вам все равно придется думать о отрицательных числах и так далее. Но это может дать вам отправную точку. Вот Demo

Удачи.