самый быстрый алгоритм, чтобы получить среднее изменение

Question

У меня есть отсортированный словарь, где ключом является дата, а значением является целое число, которое представляет оставшееся время. у меня есть данные за 3 года

так было бы что-то вроде

Ключ: 2009-1-1, Значение: 100
Ключ: 2009-1-2, Значение: 97
Ключ: 2009-1-3, значение: 92
Ключ: 2009-1-4, значение: 87 ...
...
Ключ: 2009-1-30, значение: 0

Я хотел бы рассчитать среднее изменение за день и хотел бы найти какой-нибудь элегантный способ сделать это.

Answer 1

Если значения строго нисходящие, то среднее изменение за день:

 total change = difference between time on last day and time on first day
 average change = total change / number of days

Все это можно вычислить в O (1), если вы знаете размер своего словаря.

Answer 2

Как это сделать в коде ...

Это будет обрабатывать увеличение и уменьшение:

        int changeTot = 0;
        int lastVal = 0;
        bool first = true;

        foreach (int val in myDict.Values)
        {
            if (!first) changeTot += val - lastVal;
            lastVal = val;
            first = false;
        }

        double avg = (double)changeTot / myDict.Count;

Конечно, это O (n), поскольку вы проходите массив только один раз.

Если ваши значения только увеличиваются или только уменьшаются

Вы можете использовать немного Linq:

double avg = (double)(myDict.Last().Value - myDict.First().Value) / myDict.Count();

Это будет O (1)

Answer 3

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