COMPSCI 170 Study Guide - Final Guide: Directed Acyclic Graph, Linear Programming, Topological Sorting
Document Summary
Answer the following questions, giving a short justi cation (a sentence or two). (a) suppose we have already trained two classi ers. Classi er a is a k-nearest neighbors classi er with a xed k = 25, using a linear search implementation (not a k-d tree). Classi er b is a random forest classi er with a xed t = 25 (i. e. , 25 decision trees), where each decision tree has depth at most 10. Now we want to know the running time to classify 100 test points. The running time of b is xed regardless of n, whereas the running time of a is proportional to n. Comment: if there are d dimensions, classi er a takes (nd) time to linearly scan through all of the points and (k lg k) = (1) time to keep them in a heap and nd the k closest.
