Content deleted Content added
→|G| in time complexity: new section |
→Most efficient parsing algorithm?: new section |
||
Line 101:
I'm not aware of any literature that mentions |G|. Of course the actual time the algorithm takes depends on the "size" of the grammar (I assume |G| is supposed to be the number of productions), but in this kind of problem, I've only ever seen n mentioned. In particular, in the pseudocode given, the loop over all productions is unnecessary, or at least unnecessarily specific: One would implement that as a hash table lookup, which is much faster. -- My point: If nobody disagrees, I'll erase the |G| part. -- [[User:UKoch|UKoch]] ([[User talk:UKoch|talk]]) 22:14, 9 December 2011 (UTC)
== Most efficient parsing algorithm? ==
In the article, the CYK algorithm is called ''the most efficient parsing algorithm in terms of worst-case asymptotic complexity''. Where does that come from? As discussed above, the time complexity is <math>O(n^3)</math>, and Hopcroft and Ullman mention [[Earley parser|Earley parsing]], which has the same time complexity, and they write that there's an algorithm whose time complexity is <math>O(n^{2.8})</math>, and another one whose time complexity is <math>O(n^3/\log n)</math>. (Of course, they give sources for all of these.) I'll remove the "ost efficient" part if no-one objects. -- [[User:UKoch|UKoch]] ([[User talk:UKoch|talk]]) 17:38, 14 December 2011 (UTC)
| |||