The frequent words problem

From Algorithm Wiki
Revision as of 11:01, 10 October 2022 by Admin (talk | contribs) (Created page with "== Problem Description== The problem is to find the most frequent k­mers in Text. == Bounds Chart == 1050px == Step Chart == 1050px == Improvement Table == {| class="wikitable" style="text-align:center;" width="100%" !width="20%" | Complexity Classes !! width="40%" | Algorithm Paper Links !! width="40%" | Lower Bounds Paper Links |- | rowspan="1" | Exp/Factorial | |...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

Problem Description

The problem is to find the most frequent k­mers in Text.

Bounds Chart

Finding Frequent Item setsBoundsChart.png

Step Chart

Finding Frequent Item setsStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic
nlogn
Linear [ Naive solution (1940)]

[ Rabin Karp (1987)]

logn
Retrieved from "https://algorithm-wiki.csail.mit.edu/w/index.php?title=The_frequent_words_problem&oldid=181"