Search results

Create the page "Linear time" on this wiki! See also the search results found.

• Computational geometry
  describe any point in our space. Most of the time, we will be using the Cartesian (rectangular) coordinate otherwise do something else. This is a time-consuming and error-prone way of
  83 KB (14,390 words) - 06:14, 11 April 2014
• Depth-first search
  ===Time=== ...es DFS <math>\mathcal{O}(E+V)</math> overall, [[Asymptotic analysis|linear time]], which, like [[Breadth-first search|BFS]], is asymptotically optimal for
  17 KB (2,930 words) - 00:28, 3 March 2012
• Breadth-first search
  ...r, precisely specified (yet important) problem, solves it well (in minimal time and space), and is easy to understand and to implement. ===Time===
  6 KB (1,030 words) - 23:33, 11 March 2011
• Queue
  ...make important algorithms like [[Breadth-first search|BFS]] run in linear time. To solve this, we do not replace the popped element, we merely increment a
  6 KB (1,081 words) - 04:48, 5 March 2011
• Deque
  ...make important algorithms like [[Breadth-first search|BFS]] run in linear time. To solve this, we do not replace the popped element, we merely increment a
  9 KB (1,494 words) - 03:35, 4 March 2011
• Kruskal's algorithm
  ...le implementations of Kruskal's algorithm whose running times are close to linear, usually outperforming [[Prim's algorithm]] in sparse graphs. ...haracterized as a [[greedy algorithm]], which builds the MST one edge at a time. As befits a MST algorithm, the greedy strategy is to continually add the r
  8 KB (1,403 words) - 05:47, 31 May 2011
• Heavy-light decomposition
  ...the endpoints of a path, with degree one) that gives important asymptotic time bounds for certain problems involving trees. It appears to have been introd ...on each of these, so overall this "skipping" operation runs in logarithmic time.
  9 KB (1,665 words) - 12:40, 6 August 2015
• Segment tree
  ...igned to answer the range minimum query without explicitly re-stating each time that we are doing so. Bear in mind, however, that other types of segment tr ===Time===
  21 KB (3,669 words) - 02:34, 6 April 2016
• Convex hull trick
  ...o determine ''efficiently'', after preprocessing, which member of a set of linear functions in one variable attains an extremal value for a given value of th ...nimum value of <math>y</math> that can be obtained if we select one of the linear functions and evaluate it at <math>x</math>. For example, suppose our funct
  19 KB (3,419 words) - 02:24, 13 September 2023
• Convex hull
  .... Initially we will face the right (increasing x-coordinate). At any given time we maintain both a point <math>P</math> (our location) and a [[Computationa ...points that are actually on the hull, denoted <math>h</math>, so the total time taken is <math>O(nh)</math>. In the worst case, in which <math>h=n</math> a
  18 KB (3,180 words) - 05:49, 31 May 2011
• Optimization
  ...optimization can also mean reducing disk seeks, cache faults, or response time, or increasing throughput. A specific concept that optimizes a program, suc ...timizations that do not affect asymptotic (scaling) behaviour, but improve time or memory usage by a constant factor only, see [[invisible constant factor]
  7 KB (1,155 words) - 01:34, 5 January 2012
• Longest palindromic substring
  ...h>. We now show that the problem can be solved in <math>O(N \log N)</math> time using standard data structures from the literature, the [[suffix tree]] and ..., '''as''', '''bananas''', '''nanas''', '''nas''', '''s''']. Simple linear-time algorithms now exist for computation of suffix arrays of strings with const
  19 KB (3,066 words) - 10:05, 1 November 2016
• String
  ...characters from the same alphabet can be compared for equality in constant time. ...alphabets as follows<ref>Juha Kärkkäinen and Peter Sanders. 2003. Simple linear work suffix array construction. In ''Proceedings of the 30th international
  12 KB (1,959 words) - 23:56, 23 November 2011
• Disjoint sets
  ...ust look up its representative in the table, which takes <math>O(1)</math> time. When we have to unite two sets, however, we have to pick one of these two ...ibed above supports <math>O(1)</math> find, but requires <math>O(N)</math> time for union'. What if we focus on trying to improving the speed of the union
  13 KB (2,270 words) - 01:29, 11 December 2011
• Array
  ...dex of <math>n-1</math>, we can access any object in the array in constant time just by knowing the index (using the formula for the <math>i</math><sup>th< ...sses themselves, which can be cumbersome to work with and may change every time a program is run and memory for the array allocated. If an element of an ar
  17 KB (2,904 words) - 03:08, 17 April 2012
• Graph theory
  ...ngth of time it takes to traverse the corresponding highway (''i.e.'', the time between the two cities corresponding to the vertices that the edge connects ...of a graph in which the relationships may involve more than two nodes at a time. They are generally less useful than ordinary graphs.
  25 KB (4,451 words) - 23:15, 19 October 2020
• Topological sort
  ...atrix or an adjacency list. Nor will we scan through the entire graph each time step 2 is executed in order to find a source; this, too, is computationally ...is popped). Overall, then, this algorithm takes <math>O(E+V)</math> time (linear).
  9 KB (1,677 words) - 11:36, 25 January 2012
• Longest common substring
  ...ry(ies) common to both strings. This, however, gives <math>O(n^3+m)</math> time (assuming we have two strings of lengths <math>n</math> and <math>m</math> We shall see that all three variations can be solved in linear time, no matter how many strings are given in input.
  7 KB (1,242 words) - 04:49, 29 May 2011
• Algorithm
  ...n instance of a problem is more efficient than a program that takes a long time and uses lots of memory. The technique of ''asymptotic analysis'' is genera ...to search for genes in the human genome. Using a naive <math>O(nm)</math> time algorithm for [[string searching]], approximately 10¹⁴ operation
  10 KB (1,628 words) - 18:12, 28 June 2011
• Naive algorithm
  ...irable level of [[Analysis of algorithms|efficiency]] (usually in terms of time, but also possibly memory) despite finding a correct solution or it does no ...ow needles to be "looked up" in the haystack rather than searched for in a linear fashion leads to the [[suffix tree]] data structure which reduces string se
  2 KB (297 words) - 15:24, 29 June 2011