Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2014 | OriginalPaper | Buchkapitel

6. Divide, Combine, and Conquer

verfasst von : Magnus Lie Hetland

Erschienen in: Python Algorithms

Verlag: Apress

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

■■■

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Traversal: The Skeleton Key of Algorithmics
Nächstes Kapitel Greed Is Good? Prove It!
Fußnoten
1
Note that some authors use the conquer term for the base case of the recursion, yielding the slightly different ordering: divide, conquer, and combine.
 
2
Described by Udi Manber in his Introduction to Algorithms (see “References” in Chapter 4).
 
3
For example, in the skyline problem, you would probably want to split the base case element (L,H,R) into two pairs, (L,H) and (R,H), so the combine function can build a sequence of points.
 
4
Actually, more flexible may not be entirely correct. There are many objects (such as complex numbers) that can be hashed but that cannot be compared for size.
 
5
In statistics, the median is also defined for sequences of even length. It is then the average of the two middle elements. That’s not an issue we worry about here.
 
6
In theory, we could use the guaranteed linear version of select to find the median and use that as a pivot. That’s not something likely to happen in practice, though.
 
7
Timsort is, in fact, also used in Java SE 7, for sorting arrays.
 
8
See, for example, the file listsort.txt in the source code (or online, http://svn.python.org/projects/python/ trunk/Objects/listsort.txt).
 
11
Real numbers usually aren’t all that arbitrary, of course. As long as your numbers use a fixed number of bits, you can use radix sort (mentioned in Chapter 4) and sort the values in linear time.
 
12
I think that’s so cool, I wanted to add an exclamation mark after the sentence ... but I guess that might have been a bit confusing, given the subject matter.
 
13
Actually, the approximation isn’t asymptotic in nature. If you want the details, you’ll find them in any good mathematics reference.
 
14
A region is convex if you can draw a line between any two points inside it, and the line stays inside the region.
 
15
I’m still assuming that we want a nonempty interval. If it turns out to have a negative sum, you could always use an empty interval instead.
 
16
This section is a bit hard and is not essential in order to understand the rest of the book. Feel free to skim it or even skip it entirely. You might want to read the “Black Box” sidebar on binary heaps, heapq, and heapsort, though, later in the section.
 
17
The AA-tree is, in a way, a version of the BB-tree, or the binary B-tree, which was introduced by Rudolph Bayer in 1971 as a binary representation of the 2-3-tree.
 
18
It is quite common to call this operation build-heap and to reserve the name heapify for the operation that repairs a single node. Thus, build-heap runs heapify on all nodes but the leaves.
 
Metadaten
Titel
Divide, Combine, and Conquer
verfasst von
Magnus Lie Hetland
Copyright-Jahr
2014
Verlag
Apress
Buch
Python Algorithms

Print ISBN: 978-1-4842-0056-8

Electronic ISBN: 978-1-4842-0055-1

Copyright-Jahr: 2014

DOI
https://doi.org/10.1007/978-1-4842-0055-1_6