#1 Оценка алгоритмической сложности

Primary tabs

vedro-compota's picture
Submitted by vedro-compota on Sun, 10/19/2025 - 21:11

Forums:

1. Оптимизация сложности $O(n^2)$

Классический пример сложности $O(n^2)$, это работа вложенных циклов с перебором массива из $N$ элементов без каких-либо внутренних условий, сокращающих перебор

<?php

$arr = [1, 2, 3, 4, 5];

foreach ($arr as $key1 => $value1) {
    foreach ($arr as $key2 => $value2) {
        //  if ($value1 === value2) { // какое-то сравнение
        echo "-" . ' ';
    }
    echo "\n";
}

Количество событий визуализируется так:

- - - - - 
- - - - - 
- - - - - 
- - - - - 
- - - - -

теперь начнем отступать во втором цикле, сокращая количество итераций на 1:

$arr = [1, 2, 3, 4, 5];

$start = 0;
foreach ($arr as $key1 => $value1) {
    for ($i = $start; $i < count($arr); $i++) {
        //  if ($value1 === value2) { // какое-то сравнение
        echo "-" . ' ';
    }
    $start++;
    echo "\n";
}

Получим сокращение сложности:

- - - - - 
- - - - 
- - - 
- - 
-

- в целом любые подобные "перешагивания" во вложенном цикле будут формировать зависимости подобные убывающей арифметической прогрессии, что уже меньше/быстрее чем $O(n^2)$

Сумма арифметической прогрессии

$S_n = \frac{n}{2}(a_1 + a_n)$

$S_{n}={\dfrac {2a_{1}+d(n-1)}{2}}\cdot n$

  • Log in to post comments
  • 60 reads
vedro-compota's picture

vedro-compota

Mon, 10/20/2025 - 16:13

для отладки

<?php

// $arr = [1, 2, 3, 4, 5];

// foreach ($arr as $key1 => $value1) {
//     foreach ($arr as $key2 => $value2) {
//         //  if ($value1 === value2) { // какое-то сравнение
//         echo "-" . ' ';
//     }
//     echo "\n";
// }

// теперь начнем отступать во втором цикле, сокращая количество итераций на 1


$arr = [1, 2, 3, 4, 5];

$start = 0;
foreach ($arr as $key1 => $value1) {
    for ($i = $start; $i < count($arr); $i++) {
        //  if ($value1 === value2) { // какое-то сравнение
        echo "-" . ' ';
    }
    $start++;
    echo "\n";
}

_____________
матфак вгу и остальная классика =)