Как определить алгоритмическую сложность функции?

Question

[mississippi]

У меня есть функция, нужно определить её алгоритмическую сложность, литературу вроде прочитал, но не пойму как это оформить. Помогите с данным примером пожалуйста.

<?php
function get_array_group_of_words(array $words) {        
    
    usort($words, function($a, $b) {
        return strlen($b) - strlen($a);
    });
    
    $group_of_words = [];
    $this_group = false;
    
    foreach($words as $key => $value) {
        if (!is_string($value))
            throw new \InvalidArgumentException('Массив может содержать только строки.');
        
        if ($this_group) {            
            $last = array_pop($group_of_words);
            $last[] = $value;
            array_push($group_of_words, $last);
        } else {
            
            $group_of_words[] = [$value];
        }
                
        if (isset($words[$key+1])) {
            
            $word1 = preg_split('/(?<!^)(?!$)/u', mb_strtolower($value));
            sort($word1);
            $word2 = preg_split('/(?<!^)(?!$)/u', mb_strtolower($words[$key+1]));
            sort($word2);
            
            if (strcmp(implode('', $word1), implode('', $word2)) == 0) {
                $this_group = true;
            } else {
                $this_group = false;
            }
        }
    }
    
    return $group_of_words;
}

Answer 1

[Boris Köln]

Чтобы определить алгоритмическую сложность функции надо сложить алгоритмическую сложность входящих в нее функции. Что в цикле - умножить на кол-во итераций.

литературу вроде прочитал

Если прочитали, то какая сложность у strlen?

Comments

[xmoonlight]

Boris Korobkov: O(1) )))

[Boris Köln]

xmoonlight, нет.
Чтобы узнать длину строки, надо поочередно посчитать все N элементов строки. Поэтому сложность O(N).

P.S. В PHP длина строки считается при изменении строки и значение длины кэшируется. При вызове strlen не производится подсчет, а просто отдается ранее подсчитанное значение, поэтому O(1).

[xmoonlight]

Boris Korobkov, так я имел ввиду, что операция - одна.... Поэтому и O(1)..
А если цикл - тогда другое дело: O(N)...
А вот фибоначчи, что-то не могу точно прикинуть:

function fibonacci($n)
{
    if ($n < 3) {
        return 1; 
    }
    else {
        return fibonacci($n-1) + fibonacci($n-2);
    }
}

Ban, i need help! ))

[Boris Köln]

xmoonlight, в прямом подсчете - O(N^2).
В зависимости от конкретного алгоритма это может быть O(log N).

[xmoonlight]

Boris Korobkov, ну вот я так и подумал... речь идёт именно о том алгоритме, который я написал... (со сложением...)

[xmoonlight]

Boris Korobkov, Спасибо! Просто было сомнение про O(N^2) и O(N*log(N))..

[xmoonlight]

Boris Korobkov,

В PHP длина строки считается при изменении строки и значение длины кэшируется.

А для mb_* тоже так же или нет? Откуда инфа про кэширование?

[Boris Köln]

Вариант 1: почитать исходники https://github.com/php/php-src/blob/master/ext/sta...

Вариант 2: написать тест из пары строк, миллион раз вызвать функцию для короткой строки, для длинной и сравнить время.

Answer 2

[SolidMinus]

Внутри foreach используется strcmp, имеющий сложность O(N)

Цикл также имеет такую сложность. Сложности алгоритмов вложенных перемножаются:

O(kN^2 + nlogn)

k - количество внутри алгоритмов со сложностью O(N), так как там strtolower, preg_split и т.д, то, соответственно домножается цикл O(N*(N + N + ... N)) ( в пределах одного блока сложности суммируются )

nlogn - из-за usort, я не знаю какой там алго используется, поэтому возьмем самый быстрый.

В результате округляем до того значения, который дает большой самый вклад, т.к при росте сумма nlogn становится незначительной, как и множитель k, то: O(N^2) ответ

P.S. Существует метод для не-аналитической оценки сложности алгоритма.

Берешь в цикле увеличиваешь размер входных данных и замеряешь скорость выполнения, строишь график где по Y откладываешь время, а по X - N и обычно точки ложатся в пределах какой либо функции: y=N;Y=N^2;Y=logN и т.д

Comments

[lololololo]

А что такое N?

[SolidMinus]

lololololo, размер входных данных

[lololololo]

Внутри foreach используется strcmp, имеющий сложность O(N)

Цикл также имеет такую сложность. Сложности алгоритмов вложенных перемножаются:

O(kN^2 + nlogn)

Наводящий вопрос: а это одно и то же N?

[SolidMinus]

lololololo, опечаточка была, да, одно и то же. Надо было написать N. Почитайте про оценку сложности алгоритма.

[lololololo]

strcmp имеет сложность O(длина строки). При N строках он имеет сложность O(суммарная длина строк), а вовсе не N^2

[SolidMinus]

lololololo, внимательней ответ прочитай. Он внутри цикла for, а значит strcmp будет выполняться N раз, а значит сложность O(N) превращается в O(N^2)

[lololololo]

Что этот код вообще делает? Не привык к пыховысерам.

[lololololo]

SolidMinus смотри ответ SilentFl ниже.

Answer 3

[Владимир Балин]

Цикломатическая сложность (вдруг натолкнет на нужное)

Comments

[Владимир Балин]

Статья на Википедии по этому термину

[Владимир Балин]

Кстати говоря, программы типа yEd Graph Editor поддерживают вычисление необходимых цифр, для расчета цикломатической сложности алгоритмов. Вам же останется только набросать алгоритм и посчитать на калькуляторе по формуле.

[Владимир Балин]

Заранее извиняюсь, если оффтопик

[Владимир Балин]

Еще я смотрел какую-то вводную лекцию Яндекса по тестированию, так там промелькнуло, что код не допускается к тестированию если у него цикломатическая сложность больше 5.

Answer 4

[SilentFl]

меня огорчает:
1) отсутствие описания что делает эта функция
2) странный код для определения равенства слов
3) использование флага this_group
не силен в пхп, но переписал чуть чуть получше:

// hash as sorted chars of word
// i.e. 'ababcad' -> 'aabbcd'
function word_hash($word) {
    $chars = str_split($word);
    sort($chars);
    
    return implode($chars);
}

// return grouped by word_hash array of words
function get_words_grouped_by_chars($words) {
    $hashes = [];
    $group_of_words = [];
    
    foreach($words as $key => $value) {
        if (!is_string($value))
            throw new \InvalidArgumentException('Массив может содержать только строки.');
        $hash = word_hash($value);
        if (!array_key_exists($hash, $hashes)) {
            $hashes[$hash] = $value;
            $group_of_words[$hashes[$hash]] = []; 
        }
        array_push($group_of_words[$hashes[$hash]], $value);
    }
    
    uksort($group_of_words, function($a, $b) { return strlen($b) - strlen($a); });
    return array_values($group_of_words);
}

сложность - O(N) линейная, так как используется только один цикл. НО! если есть необходимость оценить сложность прям совсем упоровшись (вместе с array_push, uksort и прочим) - то сложность по самому сложному элементу (uksort) скорее всего O(N logN), нужно смотреть документацию