Понятие функции

Чтобы выбирать наиболее эффективный алгоритм, нужно научиться оценивать, сколько он потребляет ресурсов. Для этого вспомним, что такое функция в математике.

Функция — это соответствие между элементами двух множеств, при котором каждому элементу одного множества соответствует некоторый элемент другого множества. Например,

y = x

y = x^2

или

y = x^3

Есть множество

X

и множество

Y

. Функция

f(x)

задаёт правило: как по значению из множества

X

получить соответствующее значение из множества

Y

Чтобы нарисовать график функции, можно взять несколько значений

x

, посчитать для каждого из них

y

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

Для функции

y = x

значения

x

y

совпадают. Через точки

(0, 0)

(1, 1)

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

На графике этой функции видно, что любая точка, для которой

x

y

равны, будет лежать на прямой.

Чтобы получить

y

для квадратичной функции

y = x^2,

нужно возвести значение

x

во вторую степень. Снова применим таблицу значений. Здесь двух точек для построения графика не хватит.

На основе таблицы получаем график:

Составим таблицу значений для кубической функции

y = x^3

Теперь построим график:

Функции применяются не только в математике. Каждой стране соответствует столица, каждой точке на поверхности планеты однозначно соответствуют ее широта и долгота. Это тоже примеры функций.

Когда зависимость

y

от

x

можно описать уравнением

y=kx+b

, получаем линейную функцию.

y=x

— частный случай такого уравнения при

k=1

b=0

Если зависимость у от х имеет вид

y=ax^2+bx+c

, имеем дело с квадратичной функцией.

y=x^2

— это её частный случай при

a=1, b=0, c=0

Когда уравнение зависимости у от х принимает вид

y=ax^3+bx^2+cx+d

, функция кубическая.

\\y=x^3

— её частный случай при

a=1, b=c=d=0.

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

Алгоритм с линейной зависимостью работает быстрее, то есть мы скорее получим ответ на интересующий нас вопрос. При увеличении размера входных данных объём выполняемых операций растёт не так быстро, как для двух других функций.

Убедимся в этом на примерах.

Для линейной функции

y=2

при

x=2, \

y=4

при

x=4

. Значение

y

изменилось всего на два.

В квадратичной функции

y=4

16

при тех же значениях

x

. Изменение уже более существенное.

Для кубической функции при

x=2

y=8

, а при

x=4

y=64

. Разница ещё больше.

Квадратичная функция растёт быстрее, а кубическая — ещё быстрее. Это наглядно отражено на графике.

Рассмотрим несколько примеров, которые продемонстрируют, время работы каких алгоритмов может, таким образом, зависеть от размера входных данных.

В больнице, в которую обычно ходит Гоша, работает доктор Игнатий Петрович. Он не очень общительный и часто весь день не покидает кабинет. Заходят к нему только пациенты.

Нужно определить, сколько раз в день откроется дверь в кабинет Игнатия Петровича при условии, что все пациенты, уходя, закрывают её за собой.

Каждый посетитель кабинета откроет дверь два раза. То есть количество открытий двери будет вдвое больше, чем количество вошедших. Получаем линейную зависимость, которую можно задать уравнением:

y=2\cdot x

, где

y

обозначает, сколько раз будет открываться дверь, а

x

— количество вошедших.

Другой пример. Тимофей утром встретил в лифте трёх коллег. Все поздоровались за руку. Но если людей много, так обычно не делают. Это заняло бы слишком много времени, ведь каждый должен пожать руку каждому. Здесь зависимость квадратичная. Давайте разберёмся почему.

Предположим, всего

n

человек. Каждый будет здороваться со всеми, кроме себя самого, то есть

n-1

раз.

Кажется, чтобы посчитать общее количество рукопожатий, можно воспользоваться следующим алгоритмом:

Скопировать кодPYTHON
# people - массив с именами всех встретившихся людей
handshakes_number = 0
for i in range(len(people)):
        for j in range((len(people)):
                if i != j:
                        handshakes_number += 1

Но при таком способе подсчёта каждое рукопожатие будет посчитано два раза: первый — за счет прохода по всем значениям массива счетчиком

i

, второй — счетчиком

j

. Ведь Петя здоровается с Васей и Вася с Петей — это одно рукопожатие. То есть получившееся значение переменной handshakes_number нужно разделить на 2:

Скопировать кодPYTHON
handshakes_number /= 2

Всего получается

\displaystyle n \cdot \frac{n-1}{2} = \frac{n^2-n}{2}

рукопожатий, то есть зависимость квадратичная.

Вы вспомнили основы функций и поняли, что желательно выбирать алгоритм, сложность которого имеет наименьшую скорость роста.

Эффективность алгоритмов могут оценивать не только линейной, квадратичной и кубической, но и другими видами зависимостей.

Далее вас ждут задания. В процессе их выполнения вы ненадолго снова почувствуете себя школьниками!