questionerМои знания ограничиваются тем, что один проход цикла это O(n), вложенный цикл это O(N^2) и так далее:
Но вот например merge sort:
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
public List<Integer> sort(List<Integer> list) {
if (list.size() == 1) {
return list;
} else {
List<Integer> leftPart = sort(list.subList(0, list.size() / 2));
List<Integer> rightPart = sort(list.subList(list.size() / 2, list.size()));
List<Integer> result = new ArrayList<>();
for (int i = 0, k = 0; i + k < list.size(); ) {
Integer leftMin = i < leftPart.size() ? leftPart.get(i) : null;
Integer rightMin = k < rightPart.size() ? rightPart.get(k) : null;
if (rightMin == null || (leftMin != null && leftMin < rightMin)) {
result.add(leftMin);
i++;
} else {
result.add(rightMin);
k++;
}
}
return result;
}
}
Общеизвестно, что это
O(nlogn)
n - видимо потому, что цикл. Логарифм не понимаю откуда берётся
Потому, что рекурсивное дерево обходится?
