Введение

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

Зачем тестировщику знать алгоритмы:

• Понимать сложность операций и потенциальные проблемы производительности
• Лучше планировать тестовые данные и граничные случаи
• Эффективнее общаться с разработчиками
• Создавать более качественные автоматизированные тесты
• Понимать, где могут скрываться баги

Основы алгоритмов

Что такое алгоритм?

Алгоритм - это четкая последовательность действий для решения конкретной задачи.

Свойства хорошего алгоритма:

• Конечность - алгоритм должен завершаться за конечное время
• Определенность - каждый шаг четко определен
• Результативность - алгоритм должен давать результат
• Массовость - работает для класса задач, не только для одного случая

Пример простого алгоритма:

Алгоритм поиска максимального числа в массиве:
1. Взять первый элемент как максимальный
2. Для каждого следующего элемента:
   a) Если элемент больше текущего максимума
   b) Сделать его новым максимумом
3. Вернуть максимальный элемент

Псевдокод

Псевдокод - способ записи алгоритма на языке, близком к человеческому.

Функция FindMax(массив A):
    максимум = A[0]
    Для i от 1 до длина(A) - 1:
        Если A[i] > максимум:
            максимум = A[i]
    Вернуть максимум

На JavaScript:

function findMax(array) {
    let max = array[0];
    for (let i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

Сложность алгоритмов

Big O нотация

Big O показывает, как растет время выполнения алгоритма при увеличении размера входных данных.

Основные классы сложности:

O(1) - Константная сложность:

// Доступ к элементу массива по индексу
function getElement(array, index) {
    return array[index];  // Всегда выполняется за одно действие
}

// Тестирование: время не зависит от размера массива

O(log n) - Логарифмическая сложность:

// Бинарный поиск в отсортированном массиве
function binarySearch(array, target) {
    let left = 0;
    let right = array.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (array[mid] === target) return mid;
        if (array[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

// Тестирование: для массива в 1000 элементов ~10 операций

O(n) - Линейная сложность:

// Поиск элемента в неотсортированном массиве
function linearSearch(array, target) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === target) return i;
    }
    return -1;
}

// Тестирование: время пропорционально размеру массива

O(n²) - Квадратичная сложность:

// Поиск дубликатов в массиве (неэффективный способ)
function findDuplicates(array) {
    let duplicates = [];
    for (let i = 0; i < array.length; i++) {
        for (let j = i + 1; j < array.length; j++) {
            if (array[i] === array[j]) {
                duplicates.push(array[i]);
            }
        }
    }
    return duplicates;
}

// Тестирование: для 1000 элементов ~1,000,000 операций

Практическое значение для тестирования

Планирование нагрузочных тестов:

O(1) алгоритм:
- 1,000 пользователей → 1,000 операций
- 10,000 пользователей → 10,000 операций

O(n²) алгоритм:
- 1,000 пользователей → 1,000,000 операций  
- 10,000 пользователей → 100,000,000 операций (в 100 раз больше!)

Выбор тестовых данных:

Для O(log n) алгоритма:
- Тестировать с небольшими (10 элементов) и большими (10,000) наборами
- Производительность не должна сильно отличаться

Для O(n²) алгоритма:
- Быть осторожным с большими наборами данных
- Проверять таймауты на больших объемах

Структуры данных

Массивы (Arrays)

Характеристики:

• Доступ по индексу: O(1)
• Поиск элемента: O(n)
• Вставка в конец: O(1) - амортизированная
• Вставка в середину: O(n)

Тестирование массивов:

// Граничные случаи для тестирования
const testCases = [
    [],                    // Пустой массив
    [1],                   // Один элемент
    [1, 2, 3],            // Несколько элементов
    new Array(1000).fill(0), // Большой массив
    [null, undefined, ""],  // Специальные значения
    [-1, 0, 1],           // Отрицательные, ноль, положительные
];

Объекты/Хэш-таблицы (Hash Maps)

Характеристики:

• Доступ по ключу: O(1) - в среднем
• Вставка: O(1) - в среднем
• Удаление: O(1) - в среднем

Пример использования:

// Кэш пользователей
const userCache = new Map();

function getUser(id) {
    if (userCache.has(id)) {
        return userCache.get(id);  // O(1) - быстро
    }
    
    const user = fetchUserFromDatabase(id);  // Медленно
    userCache.set(id, user);
    return user;
}

// Тестирование кэша
test('should cache user data', () => {
    const userId = 123;
    
    // Первый вызов - загружает из БД
    const user1 = getUser(userId);
    
    // Второй вызов - берет из кэша
    const user2 = getUser(userId);
    
    expect(user1).toBe(user2);  // Тот же объект
});

Списки (Lists)

Связанный список:

class ListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    
    append(value) {
        const newNode = new ListNode(value);
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.size++;
    }
    
    find(value) {
        let current = this.head;
        while (current) {
            if (current.value === value) return current;
            current = current.next;
        }
        return null;
    }
}

Тестирование связанного списка:

describe('LinkedList', () => {
    test('should append elements', () => {
        const list = new LinkedList();
        list.append(1);
        list.append(2);
        
        expect(list.size).toBe(2);
        expect(list.find(1)).toBeTruthy();
        expect(list.find(2)).toBeTruthy();
        expect(list.find(3)).toBeNull();
    });
    
    test('should handle empty list', () => {
        const list = new LinkedList();
        expect(list.find(1)).toBeNull();
        expect(list.size).toBe(0);
    });
});

Стеки и очереди

Стек (Stack) - LIFO (Last In, First Out):

class Stack {
    constructor() {
        this.items = [];
    }
    
    push(element) {
        this.items.push(element);
    }
    
    pop() {
        return this.items.pop();
    }
    
    peek() {
        return this.items[this.items.length - 1];
    }
    
    isEmpty() {
        return this.items.length === 0;
    }
}

// Пример использования: история браузера
class BrowserHistory {
    constructor() {
        this.history = new Stack();
    }
    
    visit(page) {
        this.history.push(page);
    }
    
    back() {
        if (this.history.items.length > 1) {
            this.history.pop();  // Убираем текущую страницу
            return this.history.peek();  // Возвращаем предыдущую
        }
        return null;
    }
}

Очередь (Queue) - FIFO (First In, First Out):

class Queue {
    constructor() {
        this.items = [];
    }
    
    enqueue(element) {
        this.items.push(element);
    }
    
    dequeue() {
        return this.items.shift();
    }
    
    front() {
        return this.items[0];
    }
    
    isEmpty() {
        return this.items.length === 0;
    }
}

// Пример использования: очередь задач
class TaskQueue {
    constructor() {
        this.queue = new Queue();
        this.processing = false;
    }
    
    addTask(task) {
        this.queue.enqueue(task);
        this.processNext();
    }
    
    async processNext() {
        if (this.processing || this.queue.isEmpty()) return;
        
        this.processing = true;
        const task = this.queue.dequeue();
        
        try {
            await task.execute();
        } catch (error) {
            console.error('Task failed:', error);
        }
        
        this.processing = false;
        this.processNext();  // Обработать следующую задачу
    }
}

Алгоритмы сортировки

Пузырьковая сортировка (Bubble Sort)

Сложность: O(n²)

function bubbleSort(array) {
    const n = array.length;
    for (let i = 0; i < n - 1; i++) {
        for (let j = 0; j < n - i - 1; j++) {
            if (array[j] > array[j + 1]) {
                // Обмен элементов
                [array[j], array[j + 1]] = [array[j + 1], array[j]];
            }
        }
    }
    return array;
}

// Тестирование
const testArrays = [
    [],
    [1],
    [3, 1, 2],
    [5, 4, 3, 2, 1],  // Худший случай
    [1, 2, 3, 4, 5],  // Лучший случай
    [2, 2, 2, 2],     // Одинаковые элементы
];

Быстрая сортировка (Quick Sort)

Сложность: O(n log n) - в среднем, O(n²) - в худшем случае

function quickSort(array, low = 0, high = array.length - 1) {
    if (low < high) {
        const pivotIndex = partition(array, low, high);
        quickSort(array, low, pivotIndex - 1);
        quickSort(array, pivotIndex + 1, high);
    }
    return array;
}

function partition(array, low, high) {
    const pivot = array[high];
    let i = low - 1;
    
    for (let j = low; j < high; j++) {
        if (array[j] <= pivot) {
            i++;
            [array[i], array[j]] = [array[j], array[i]];
        }
    }
    
    [array[i + 1], array[high]] = [array[high], array[i + 1]];
    return i + 1;
}

// Тестирование производительности
function measureSortingTime(sortFunction, array) {
    const start = performance.now();
    sortFunction([...array]);  // Копия для чистого теста
    const end = performance.now();
    return end - start;
}

Алгоритмы поиска

Линейный поиск

Сложность: O(n)

function linearSearch(array, target) {
    for (let i = 0; i < array.length; i++) {
        if (array[i] === target) {
            return i;
        }
    }
    return -1;
}

// Тестирование различных случаев
describe('Linear Search', () => {
    const array = [1, 3, 5, 7, 9];
    
    test('should find existing element', () => {
        expect(linearSearch(array, 5)).toBe(2);
    });
    
    test('should return -1 for non-existing element', () => {
        expect(linearSearch(array, 6)).toBe(-1);
    });
    
    test('should find first element', () => {
        expect(linearSearch(array, 1)).toBe(0);
    });
    
    test('should find last element', () => {
        expect(linearSearch(array, 9)).toBe(4);
    });
});

Бинарный поиск

Сложность: O(log n) Требование: Массив должен быть отсортирован

function binarySearch(array, target) {
    let left = 0;
    let right = array.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (array[mid] === target) {
            return mid;
        } else if (array[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

// Тестирование бинарного поиска
describe('Binary Search', () => {
    test('should work with sorted array', () => {
        const sorted = [1, 3, 5, 7, 9, 11, 13];
        expect(binarySearch(sorted, 7)).toBe(3);
        expect(binarySearch(sorted, 1)).toBe(0);
        expect(binarySearch(sorted, 13)).toBe(6);
        expect(binarySearch(sorted, 6)).toBe(-1);
    });
    
    test('should handle edge cases', () => {
        expect(binarySearch([], 5)).toBe(-1);
        expect(binarySearch([5], 5)).toBe(0);
        expect(binarySearch([5], 3)).toBe(-1);
    });
});

Рекурсия

Основы рекурсии

Рекурсия - это когда функция вызывает саму себя.

Компоненты рекурсивной функции:

1. Базовый случай - условие остановки
2. Рекурсивный случай - вызов функции с измененными параметрами

// Факториал числа
function factorial(n) {
    // Базовый случай
    if (n <= 1) {
        return 1;
    }
    
    // Рекурсивный случай
    return n * factorial(n - 1);
}

// Тестирование рекурсии
describe('Factorial', () => {
    test('should calculate factorial correctly', () => {
        expect(factorial(0)).toBe(1);
        expect(factorial(1)).toBe(1);
        expect(factorial(5)).toBe(120);
        expect(factorial(10)).toBe(3628800);
    });
    
    test('should handle large numbers', () => {
        // Проверка на переполнение стека
        expect(() => factorial(10000)).toThrow();
    });
});

Числа Фибоначчи

Неэффективная рекурсия:

function fibonacciSlow(n) {
    if (n <= 1) return n;
    return fibonacciSlow(n - 1) + fibonacciSlow(n - 2);
}

// Сложность: O(2^n) - очень медленно!

Эффективная рекурсия с мемоизацией:

function fibonacciFast(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 1) return n;
    
    memo[n] = fibonacciFast(n - 1, memo) + fibonacciFast(n - 2, memo);
    return memo[n];
}

// Сложность: O(n) - гораздо быстрее!

// Тестирование производительности
test('memoization should improve performance', () => {
    const start1 = performance.now();
    fibonacciSlow(35);
    const time1 = performance.now() - start1;
    
    const start2 = performance.now();
    fibonacciFast(35);
    const time2 = performance.now() - start2;
    
    expect(time2).toBeLessThan(time1 / 100);  // Мемоизация в 100+ раз быстрее
});

Устройство программ

Переменные и память

Типы данных и их размеры:

// Примитивные типы
let number = 42;           // 8 байт (double precision)
let string = "Hello";      // Зависит от длины
let boolean = true;        // 1 байт
let nullValue = null;      // Специальное значение
let undefinedValue;        // Специальное значение

// Ссылочные типы
let array = [1, 2, 3];     // Ссылка на объект в куче
let object = {name: "John"}; // Ссылка на объект в куче

// Тестирование работы с памятью
test('primitive vs reference types', () => {
    let a = 5;
    let b = a;  // Копирование значения
    a = 10;
    expect(b).toBe(5);  // b не изменилось
    
    let obj1 = {value: 5};
    let obj2 = obj1;  // Копирование ссылки
    obj1.value = 10;
    expect(obj2.value).toBe(10);  // obj2 изменилось!
});

Стек и куча

Стек (Stack):

• Хранит примитивные типы и ссылки
• Быстрый доступ
• Ограниченный размер
• Автоматическое управление памятью

Куча (Heap):

• Хранит объекты и массивы
• Медленнее доступ
• Больший размер
• Требует сборки мусора

function demonstrateMemory() {
    // Хранится в стеке
    let x = 10;
    let y = 20;
    
    // Ссылки хранятся в стеке, объекты в куче
    let person = {name: "John", age: 30};
    let numbers = [1, 2, 3, 4, 5];
    
    return {person, numbers};
}

// Тестирование утечек памяти
test('should not leak memory', () => {
    const initialMemory = process.memoryUsage().heapUsed;
    
    for (let i = 0; i < 1000; i++) {
        let largeArray = new Array(1000).fill(i);
        // Массив должен быть очищен в конце итерации
    }
    
    // Принудительная сборка мусора (если доступна)
    if (global.gc) global.gc();
    
    const finalMemory = process.memoryUsage().heapUsed;
    const memoryIncrease = finalMemory - initialMemory;
    
    // Проверяем, что память не увеличилась значительно
    expect(memoryIncrease).toBeLessThan(1024 * 1024); // Меньше 1MB
});

Циклы и их производительность

Цикл for:

function sumWithFor(numbers) {
    let sum = 0;
    for (let i = 0; i < numbers.length; i++) {
        sum += numbers[i];
    }
    return sum;
}

Цикл for...of:

function sumWithForOf(numbers) {
    let sum = 0;
    for (const number of numbers) {
        sum += number;
    }
    return sum;
}

Функциональный стиль:

function sumWithReduce(numbers) {
    return numbers.reduce((sum, number) => sum + number, 0);
}

// Тестирование производительности циклов
function benchmarkLoops() {
    const largeArray = new Array(1000000).fill(1);
    
    console.time('for loop');
    sumWithFor(largeArray);
    console.timeEnd('for loop');
    
    console.time('for...of loop');
    sumWithForOf(largeArray);
    console.timeEnd('for...of loop');
    
    console.time('reduce');
    sumWithReduce(largeArray);
    console.timeEnd('reduce');
}

Условные операторы

Простые условия:

function getGrade(score) {
    if (score >= 90) return 'A';
    if (score >= 80) return 'B';
    if (score >= 70) return 'C';
    if (score >= 60) return 'D';
    return 'F';
}

// Тестирование граничных случаев
describe('Grade calculation', () => {
    test('boundary values', () => {
        expect(getGrade(90)).toBe('A');  // Граница A
        expect(getGrade(89)).toBe('B');  // Граница B
        expect(getGrade(80)).toBe('B');  // Граница B
        expect(getGrade(79)).toBe('C');  // Граница C
    });
    
    test('edge cases', () => {
        expect(getGrade(0)).toBe('F');
        expect(getGrade(100)).toBe('A');
        expect(getGrade(-1)).toBe('F');    // Отрицательное число
        expect(getGrade(101)).toBe('A');   // Больше максимума
    });
});

Switch statement:

function getDayType(day) {
    switch (day.toLowerCase()) {
        case 'monday':
        case 'tuesday':
        case 'wednesday':
        case 'thursday':
        case 'friday':
            return 'weekday';
        case 'saturday':
        case 'sunday':
            return 'weekend';
        default:
            return 'invalid';
    }
}

// Тестирование switch
test('day type classification', () => {
    expect(getDayType('Monday')).toBe('weekday');
    expect(getDayType('SATURDAY')).toBe('weekend');
    expect(getDayType('invalid')).toBe('invalid');
    expect(getDayType('')).toBe('invalid');
});

Обработка ошибок

Try-Catch блоки

function divideNumbers(a, b) {
    try {
        if (b === 0) {
            throw new Error('Division by zero is not allowed');
        }
        return a / b;
    } catch (error) {
        console.error('Error in division:', error.message);
        return null;
    }
}

// Тестирование обработки ошибок
describe('Error handling', () => {
    test('should handle division by zero', () => {
        expect(divideNumbers(10, 0)).toBeNull();
    });
    
    test('should perform normal division', () => {
        expect(divideNumbers(10, 2)).toBe(5);
    });
    
    test('should throw error for invalid input', () => {
        expect(() => {
            throw new Error('Test error');
        }).toThrow('Test error');
    });
});

Асинхронная обработка ошибок

async function fetchUserData(userId) {
    try {
        const response = await fetch(`/api/users/${userId}`);
        
        if (!response.ok) {
            throw new Error(`HTTP error! status: ${response.status}`);
        }
        
        const userData = await response.json();
        return userData;
    } catch (error) {
        console.error('Failed to fetch user data:', error);
        throw error;  // Передаем ошибку дальше
    }
}

// Тестирование асинхронных ошибок
test('should handle fetch errors', async () => {
    // Мокаем fetch для возврата ошибки
    global.fetch = jest.fn(() =>
        Promise.resolve({
            ok: false,
            status: 404,
        })
    );
    
    await expect(fetchUserData(123)).rejects.toThrow('HTTP error! status: 404');
});

Практические рекомендации для тестирования

Граничные случаи (Edge Cases)

Числовые границы:

function testNumericBoundaries(value) {
    const testCases = [
        0,                    // Ноль
        1,                    // Минимальное положительное
        -1,                   // Минимальное отрицательное
        Number.MAX_VALUE,     // Максимальное число
        Number.MIN_VALUE,     // Минимальное положительное число
        Number.POSITIVE_INFINITY,
        Number.NEGATIVE_INFINITY,
        Number.NaN,           // Not a Number
    ];
    
    return testCases.map(testCase => ({
        input: testCase,
        result: yourFunction(testCase)
    }));
}

Строковые границы:

function testStringBoundaries(str) {
    const testCases = [
        "",                   // Пустая строка
        " ",                  // Пробел
        "a",                  // Один символ
        "A".repeat(1000),     // Очень длинная строка
        "тест",               // Unicode символы
        "🚀",                 // Emoji
        "\n\t\r",            // Специальные символы
        null,                 // null
        undefined,            // undefined
    ];
    
    return testCases.map(testCase => ({
        input: testCase,
        result: yourFunction(testCase)
    }));
}

Тестирование производительности

function performanceTest(algorithm, testData) {
    const iterations = 1000;
    const start = performance.now();
    
    for (let i = 0; i < iterations; i++) {
        algorithm(testData);
    }
    
    const end = performance.now();
    const averageTime = (end - start) / iterations;
    
    return {
        totalTime: end - start,
        averageTime: averageTime,
        iterations: iterations
    };
}

// Сравнение алгоритмов
test('compare sorting algorithms performance', () => {
    const testData = Array.from({length: 1000}, () => Math.random());
    
    const bubbleSortResult = performanceTest(bubbleSort, testData);
    const quickSortResult = performanceTest(quickSort, testData);
    
    // Quick Sort должна быть быстрее Bubble Sort
    expect(quickSortResult.averageTime).toBeLessThan(bubbleSortResult.averageTime);
});

Тестирование алгоритмической корректности

function testSortingCorrectness(sortFunction) {
    const testCases = [
        [],
        [1],
        [2, 1],
        [3, 1, 2],
        [5, 4, 3, 2, 1],     // Обратно отсортированный
        [1, 2, 3, 4, 5],     // Уже отсортированный
        [3, 3, 3, 3],        // Одинаковые элементы
        [-3, -1, 0, 2, 4],   // Отрицательные числа
    ];
    
    testCases.forEach(testCase => {
        const original = [...testCase];
        const sorted = sortFunction([...testCase]);
        
        // Проверяем, что массив отсортирован
        for (let i = 1; i < sorted.length; i++) {
            expect(sorted[i]).toBeGreaterThanOrEqual(sorted[i-1]);
        }
        
        // Проверяем, что все элементы сохранились
        expect(sorted.sort()).toEqual(original.sort());
    });
}

Заключение

Понимание алгоритмов и устройства программ дает тестировщику:

• Лучшее понимание производительности - где могут быть узкие места
• Более эффективное планирование тестов - какие данные использовать
• Понимание граничных случаев - где вероятнее всего ошибки
• Эффективную коммуникацию с разработчиками - общий технический язык
• Навыки автоматизации - написание качественных тестов

Эти знания особенно важны при тестировании:

• Производительности приложений
• Обработки больших объемов данных
• Алгоритмически сложных функций
• Критически важных вычислений

Помните: вам не нужно быть экспертом в алгоритмах, но базовое понимание значительно повысит качество вашего тестирования.