Insights Blog
-- Browse All Articles --
Physics Articles
Physics Tutorials
Physics Guides
Physics FAQ
Math Articles
Math Tutorials
Math Guides
Math FAQ
Education Articles
Education Guides
Bio/Chem Articles
Technology Guides
Computer Science Tutorials
Forums
Chemistry
Biology and Medical
Earth Sciences
Computer Science
Computing and Technology
DIY Projects
Trending
Featured Threads
Log in
Register
What's new
Search
Search
Search titles only
By:
Chemistry
Biology and Medical
Earth Sciences
Computer Science
Computing and Technology
DIY Projects
Menu
Log in
Register
Navigation
More options
Contact us
Close Menu
JavaScript is disabled. For a better experience, please enable JavaScript in your browser before proceeding.
You are using an out of date browser. It may not display this or other websites correctly.
You should upgrade or use an
alternative browser
.
Forums
Other Sciences
Programming and Computer Science
Running time of FirstFit(FF): Original and Improved version
Reply to thread
Message
[QUOTE="QuantumQuest, post: 6331957, member: 554291"] My question is, have you studied the pseudocode for this? I ask because, the way you write it, seems that you're trying to understand it somewhat in the abstract. This is not necessarily wrong but studying the pseudocode of an algorithm is helpful in any case and particularly when you have any doubt. If you study the pseudocode, you'll see in which case and why the running time of the FF algorithm yields an asymptotical ##O(n^2)##. In short, the [I]worst case[/I] is the one in which a new bin has to be opened for each new insertion of an object. Now, one very important use of this FF algorithm is as a partition selection algorithm in operating systems i.e. selecting free memory to accommodate a process. A high level way in which it works is: The OS looks at the whole of the sections of free memory. The process is allocated to the [I]first [/I]hole found that is larger regarding the size of the process. If the size of the process matches the size of the hole then there is (obviously) no hole anymore otherwise the hole continues to exist but reduced by the size of the process. First Fit is a fast method but not necessarily an optimal one. [URL='https://en.wikipedia.org/wiki/Segment_tree']Segment Tree[/URL] Also, take note that the segment tree is not the only way to achieve ##O(n\log n)## worst-case running time. You can also use other heuristics as well, like a [I]priority queue, [/I]to accommodate, for example, the bins with [I]maximum remaining capacity[/I] so, effectively, you'll have one loop for objects and a priority quee for bins yielding an ##O(n \cdot \log n)## worst-case running time. [/QUOTE]
Insert quotes…
Post reply
Forums
Other Sciences
Programming and Computer Science
Running time of FirstFit(FF): Original and Improved version
Back
Top