Calcul des asymptotiques - 9
Задача
Pour le code ci-dessous, recherchez les asymptotiques :
#include <bits/stdc++.h>
en utilisant l'espace de noms std ;
int main()
{
entier n, m ;
vecteur < vecteur<int> > up1(n, vecteur <int>(m));
int et = 0 ;
pour (int i = 1 ; je <= n; je++)
{
vecteur <int> L(m + 1, 1< /span>), R(m + 1, m);
empiler <int>q ;
pour (int j = 1 ; j <= m; j++)
{
tandis que (!q.empty() && up1 [i][j] < up1[i][q.top()])
{
R[q.top()] = j - 1 ;
q.pop();
}
qpush(j);
}
tandis que (!q.empty())
q.pop();
pour (int j = m; j >= 1 ; j--)
{
tandis que (!q.empty() && up1 [i][j] < up1[i][q.top()])
{
L[q.top()] = j + 1 ;
q.pop();
}
qpush(j);
}
pour (int j = 1 ; j <= m; j++)
ans = max(ans, up1[i][j] * (R[j] < span style="color:#666666">- L[j] + 1) );
}
cout << ans ;
retour 0 ;
}
1) O(n+m) 2) O(nm) 3) O(n^2*m) 4) O(n*m^2)
Выберите правильный ответ, либо введите его в поле ввода
Комментарий учителя