frequency table

• When there are N numbers and N is too large to do O(N^2)

• If the order of the numbers is meaningless and the number type is M, which is much less than N

• Creating a frequency table by type can reduce the amount of calculations.

• Frequency→Triangular number

• For any pair of two choices of N numbers, the case where two have the same value is counted

• A naive loop is O(N^2)

• Count the frequencies and for each value frequency n trigonometric number $T_{n-1}=n(n-1)/2$.

  • This would be O(N)

• multiset 、multiset

---

This page is auto-translated from /nishio/頻度表 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.