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

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

<?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;
}
  • Вопрос задан
  • 1980 просмотров
Пригласить эксперта
Ответы на вопрос 4
@BorisKorobkov Куратор тега PHP
Web developer
Чтобы определить алгоритмическую сложность функции надо сложить алгоритмическую сложность входящих в нее функции. Что в цикле - умножить на кол-во итераций.

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

Если прочитали, то какая сложность у strlen?
Ответ написан
@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 и т.д
Ответ написан
Цикломатическая сложность (вдруг натолкнет на нужное)
Ответ написан
@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), нужно смотреть документацию
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы