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

1. Рекурсивно найти n-ое число Фибоначчи.

Определить какая здесь будет сложность.

(fn[0] = 0 или 1)

[fn(n) = fn(n - 1) + fn(n - 2)]

2.Найти n-ое число Фибоначчи за O(n). (за О от (n); за линейную сложность)

3.Найти сумму элементов главной диагонали в двумерном массиве. Найти сумму элементов побочной диагонали в двумерном массиве.

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

1 2 3 4 5

```java

public void findMainDiagonalSum(int[][] matrix) {

// TODO: 12.01.2023

}

Если матрица не квадратная, то будем считать, что это ошибка.

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

4. Реализовать сдвиг элементов в массиве на n влево или вправо.

```java

// Пример:  [1, 2, 3, 4], n = 1 => [4, 1, 2, 3]

public void shift(int[] array) {

    // TODO: 12.01.2023 

}