Created
December 19, 2023 05:10
-
-
Save dfer/8c81ff45335e7fc7cce364e36766e563 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| """Пример применения медианного сглаживания для массива t и шириной окна n""" | |
| """ | |
| Вычислительная сложность будет O(n), то есть в нашем случае O(t), чтобы не запутаться в обозначениях. | |
| Мы бежим по массиву из t элементов. Это уже O(t). | |
| В рамках обработки каждого элемента массива, мы или копируем элемент в результирующий массив, то есть обращаемся к нему - это O(1), | |
| либо обращаемся к нескольким последовательным элементам массива. Скажем t[a:b] - имеет вычислительную сложность O(b-a). | |
| Плюс мы создаем новый массив, в котором накапливаем результат. На его создание тоже надо O(t). | |
| Получается, что вся вычислительная сложность алгоритма O(t). Или, если в стандартных терминах, O(n). | |
| """ | |
| t = [1,2,3,4,5,6,7,8,9] | |
| n = 4 | |
| result_t = [] | |
| def calculate_median(numbers): | |
| length = len(numbers) | |
| if length % 2 == 0: | |
| median = (numbers[length // 2] + numbers[length // 2 - 1]) / 2 | |
| else: | |
| median = numbers[length // 2] | |
| return median | |
| for i in range(len(t)): | |
| if i >= n: | |
| result_t.append(calculate_median(result_t[i-n:i])) | |
| else: | |
| result_t.append(t[i]) | |
| print(result_t) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment