Линейная сложность $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 числам. Это и есть линейная сложность — количество шагов растёт пропорционально размеру входных данных.