Complexitate O(n4)
Se fixeaza un colt al patratului pe care il analizam (complexitate O(n2)) - cel mai simplu, cel din dreapta sus. Se mai fixeaza apoi si latura patratului. Cu aceste trei elemente determinate (coordonatele unui colt, respectiv latura patratului), acesta este unic determinat. Acum, tot ce mai avem de facut este sa iteram printre elementele conturului patratului selectat si sa le aflam suma. Fixarea lungimii laturii si iterarea printre elementele perimetrului sau iau inca O(n2) timp de executie, deci, complexitatea timp totala a acestei prime solutii este O(n4). Complexitate O(n3)
Cu o simpla observatie, putem reduce complexitatea solutiei de mai sus la O(n3). Observam ca daca avem un patrat cu colturile in (x1,y1), respectiv in (x2,y2), suma elementelor conturului sau se poate exprima ca suma a doua intervale de linii si a doua intervale de coloane. Concret, ne vom folosi de tehnica sumelor partiale pentru a reduce complexitatea rezolvarii de mai sus cu un ordin de N. Astfel, vom precalcula 2 matrici h[i][j] si v[i][j] dupa urmatoarea recurenta: h[i][j]=h[i][j-1]+mat[i][j] v[i][j]=v[i-1][j]+mat[i][j]unde
h[i][0]=0 si v[0][j]=0 Acum, in functie de implementare, este posibil sa avem un caz particular pentru subpatratele de latura 1. In general, suma conturului patratului cu colturile in (x1,y1), respectiv in (x2,y2) este h[x2][y2]-h[x2][y1-1]+h[x1][y2]-h[x1][y1-1]+v[x2-1][y2]-v[x1][y2]+v[x2-1][y2]-v[x1][y2] Formula de mai sus poate parea complicata, dar, daca cititorul va incerca sa o deduca singur o va intelege cu siguranta.
Asadar, aflarea sumei de pe contur a fost coborata de la O(n) la O(1) printr-o preprocesare in O(n2), aceasta neafectand insa complexitatea totala a algoritmului.
Complexitate totala: O(n3)
Lasam ca tema de gandire cititorului rezolvarea problemei in cazul in care avem lucram cu dreptunghiuri in loc de patrate in complexitate O(n4). Mentionez ca in acest caz exista o arie mult mai variata de cazuri particulare ce vor trebui tratate. O alta idee interesanta este rezolvarea problemei cu produse in loc de sume in O(n3) pentru cazul cu patrate (extensia pentru cazul cu dreptunghiuri devenind triviala ca idee in cazul in care deja se cunoaste solutia pentru problema cu sume pe dreptunghiuri).
