Aşağıdaki kodun zaman karmaşıklığı nedir ve bunu doğrusal veya logaritmik zaman karmaşıklığına nasıl değiştirebilirim?

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; 

Sanırım o (n^n) değilse, zaman karmaşıklığını ve nasıl olduğunu söyleyiniz?
Ve ikinci olarak kod, doğrusal veya logaritmik zaman karmaşıklığı içinde dönüştürülebilir. Veri Yapıları ve algoritmaları alanında yeniim. Lütfen bu sorunu çözmek için bana yardımcı olun.
Kodu verirseniz harika olur. Teşekkürler :)

Answer 1

İnsanların neden bu soruya oy verdiklerini anlamıyorum. Oldukça ilginç.

Tüm girişler pozitif sayılarsa, istediğiniz sonuç aslında ikinci maksimum değerdir. Kendin kodlayabileceğine inanıyorum. Kanıt, sonuçta bir sayı modunun maksimum sayı olması, ikinci en büyük sayı modunun en iyi sonucu vermesi ve ikinci en büyük sayıya eşdeğer olması gerektiğidir. Fakat birden fazla maksimum sayı varsa dikkatli olun, en büyük olanı kontrol etmeniz gerekir.

Bazı sayılar negatifse, biraz yanıltıcı olabilir. Modülün sonucunun her zaman olumlu olduğunu düşünüyorum. (C'de bu şekilde çalışmıyor olsa da, bu durumda bu negatif sayıları görmezden gelebilirsiniz). Önce tüm negatif sayılar pozitif hale getirilirken, dizinin bir kopyasına ihtiyacımız var. İkincisi, iki diziden üç sayıya, ikinci dizinin ikinci maksimum pozitif ve en büyük negatif numarasına (0'a en yakın olanı) ve ikinci diziden en büyük sayıya (tümü pozitif değere dönüştürülmüş) ihtiyacımız var. Üçüncü sayıdaki ilk iki sayıyı karşılaştırın, daha büyük olanı çıkarın.

Answer 2

Orijinal kodunuzu hazırladım, böylece bir başlangıç ​​noktanız var.

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; 
} 

Senin sorunun aslında oldukça ilginç ve (uygulama 03 C++ kadar tanımlanmış olan) modülo operasyonun işareti sözleşmeler bağlıdır. Genel olarak, az sayıda araştırmayı bazı dönüşümlerle birleştirerek doğrusal zamanda çözülmesi mümkün olmalıdır. İşte bu, tüm girişler için geçerli değildir. Bu bir ilk lineer giriftir . Ve hala negatif sayılar hakkında düşünmek zorundasın. Ama size bir başlangıç ​​noktası verebilir. İşte iyi şanslar.