[PHP]złożoność algorytmu. time complexity O(N) vs O(N * N) Opcje

[porzeczki]

pomijając jakość poniższego algorytmu, co sprawia że ma time complexity O(N * N) a nie O(N)? if w pętli for czy foreach obok for?

[PHP] pobierz, plaintext 
    private function solution(array $A)
    {
 
        $najniższaWB=0;
        foreach($A as $value){
            $najniższaWB += abs($value);
        }
 
        $r=abs($A);
 
        $wartoscBezwzgl=[];
 
        for($i=1;$i<count($A)+1;$i++)
        {
            $right = array_sum(array_slice($A,$i));
            $left = array_sum(array_slice($A,0,$i));
 
            $wartoscBezwzgl = abs($left-$right);
 
            if ($wartoscBezwzgl < $najniższaWB){
                $najniższaWB=$wartoscBezwzgl;
            }
 
        }
 
        return $najniższaWB;
    }
[PHP] pobierz, plaintext 

[SmokAnalog]

Moim zdaniem na taką złożoność składa się tu array_sum w for, a count w warunku for też nie pomaga. Zoptymalizuj to, nie musisz przecież liczyć całej sumy za każdym razem od nowa, skoro odejmujesz tylko jeden element. A count trzymaj w zmiennej.

[porzeczki]

przeniosłem count i dalej jest O(N*N). Też mi się wydaje, że array_sum albo array_slice.

[SmokAnalog]

No tak, dalej tak będzie. Zlicz sumę i po kolei odejmuj od niej określone elementy zanim obliczać sumę z wycinka tablicy. Wtedy będzie O(n).

[porzeczki]

ok, dzięki

[Pyton_000]

http://stackoverflow.com/a/33474486/3732803

[SmokAnalog]

Są jakieś narzędzia online, które mierzą złożoność funkcji napisanych w PHP?