Линейная сложность $O(n)$ означает, что время выполнения алгоритма растёт пропорционально размеру входных данных $n$. Если у вас есть 10 элементов, алгоритм выполнится за 10 шагов; если 1000 элементов — за 1000 шагов. ### Простой пример Представьте, что у вас есть список из 100 чисел, и вам нужно найти определённое число в этом списке. Самый простой способ это сделать — это пройтись по каждому числу в списке и сравнить его с искомым. #### Код на C\# ```csharp public static int LinearSearch(int[] array, int target) { for (int i = 0; i < array.Length; i++) { if (array[i] == target) { return i; } } return -1; // Элемент не найден } ``` #### Производительность Если искомое число будет первым в списке, алгоритм выполнится за 1 шаг. Если последним — за 100 шагов. В среднем, ему потребуется 50 шагов. Но в худшем случае (или если числа нет в списке) ему всё равно придётся пройтись по всем 100 числам. Это и есть линейная сложность — количество шагов растёт пропорционально размеру входных данных.