Оценка сложности алгоритмов

algorithms.js

/**
 * Поиск дублирующихся символов.
 *
 * Сложность: f(n) = 4 + 4n + 8n² = O(n²)
 *
 * @param {string} str строка для поиска совпадений
 * @returns {array} только дублирующиеся символы
 */
function duplicationSymbols(str = '') {
    const dupSymbols = {};

    for (let i = 0; i < str.length; i++) {
        for (let j = 0; j < str.length; j++) {
            if (i !== j && str[i] === str[j]) { // сравнение и поиск по ключу это инструкций, тут 4 инструкции
                dupSymbols[str[i]] = '';
                break;
            }
        }
    }

    return Object.keys(dupSymbols);
}

duplicationSymbols('atesta');

/**
 * Сортировка выбором.
 *
 * Сложность на первой итерации: f(n) = 5 + 6n + 3n² = O(n²)
 * Сложность на второй итерации: f(n) = 5 + 6n + 3(n-1)² = O(n²)
 * Сложность на третей итерации: f(n) = 5 + 6n + 3(n-2)² = O(n²)
 *
 * @param {array} arr массив для сортировки
 * @returns {array} отсортированный массив
 */
function sortPick(arr = []) {
    const sorted = [];

    for (let i = 0, len = arr.length; i < len; i++) {
        let min = arr[0];
        let minIndex = 0;

        for (let j = 0; j < arr.length; j++) { // с каждой итерацией родительского цикла, в этом цикле уменьшается кол-во элементов (3n², 3(n-1)², 3(n-2)²)
            if (arr[j] < min) {
                min = arr[j];
                minIndex = j;
            }
        }

        arr.splice(minIndex, 1);
        sorted.push(min);
    }

    return sorted;
}

sortPick([2,5,2,3,8,4,0,9]);

/**
 * Арифметическая прогрессия
 *
 * Сложность: f(n) = 4 + 5n = O(n)
 *
 * @param {number} initial начальное значение
 * @param {number} step шаг итерации
 * @param {number} length длина ряда
 * @returns {array} ряд чисел
 */
function arithmeticProgression(initial = 1, step = 1, length = 10) {
    const series = [];

    for (let i = 0; i < length; i++) {
        series.push(initial + step * i);
    }

    return series;
}

arithmeticProgression(2, 5, 5);


/**
 * Простейший архиватор
 *
 * Сложность: f(n) = 5 + 13n = O(n)
 *
 * @param {string} str строка для архивирования
 * @returns {string} архивированая строка
 */
function archiver(str = '') {
    let result = '';
    let counter = 0;

    for (let i = 0; i < str.length; i++) {
        let cur = str[i];

        if (cur === str[i + 1]) {
            counter += 1;
            continue;
        }

        result += (counter > 1 ? counter : '') + cur;
        counter = 1;
    }

    return result;
}

archiver('AAAAAAAZZZZEEDSSSSAZZZZP');

/**
 * Преобразование арабский цифр в римские
 * На этом задании я погорел когда проходил интервью в ЯД :)
 *
 * Сложность: f(n) = 7 + 9n = O(n)
 *
 * @param {number} num арабские цифры для преобразования
 * @returns {string} римские цифры
 */
function arabicToRoman(num) {
    const mapping = {
        1: 'I',
        2: 'II',
        3: 'III',
        4: 'IV',
        5: 'V',
        6: 'VI',
        7: 'VII',
        8: 'VIII',
        9: 'IX',
        10: 'X',
        20: 'XX',
        30: 'XXX',
        40: 'XL',
        50: 'L',
        60: 'LX',
        70: 'LXX',
        80: 'LXXX',
        90: 'XC',
        100: 'C',
        200: 'CC',
        300: 'CCC',
        400: 'CD',
        500: 'D',
        600: 'DC',
        700: 'DCC',
        800: 'DCCC',
        900: 'CM',
        1000: 'M',
    };

    const str = String(num);
    let romans = '';

    for (let i = str.length; i > 0; i--) {
        const sym = str[str.length - i] + '0'.repeat(i - 1);
        romans += mapping[sym];
    }

    return romans;
}

arabicToRoman(954);

/**
 * Найти все пересечения массивов
 */
// code...


/**
 * Разбить массив по чанкам заданного размера
 *
 * Сложность: f(n) = 8 + 7n = O(n)
 *
 * @param {array} array массив для разбиения
 * @param {number} size размер чанка
 * @returns {array} разбитый по чанкам массив
 */
function chunk(array, size = 1) {
    const chunked = [];
    const chunkCount = Math.ceil(array.length / size);

    for (let i = 0; i < chunkCount; i++) {
        chunked.push(array.slice(size * i, size * i + size));
    }

    return chunked;
}

chunk([1,1,2,2,3,3,4], 2)