Content deleted Content added
→Background: linking |
|||
Line 36:
*A [[Set (abstract data type)|set]] of employers with unfilled positions
*A one-dimensional [[Array (data structure)|array]] indexed by employers, specifying the preference index of the next applicant to whom the employer would send an offer, initially 1 for each employer
*A two-dimensional array indexed by an employer and a number <math>i</math> from 1 to <math>n</math>, naming the applicant who is each employer's {{nowrap|<math>i</math>th}} preference▼
*A one-dimensional array indexed by applicants, specifying their current employer, initially a [[sentinel value]] such as 0 indicating they are unemployed
*A two-dimensional array indexed by an applicant and an employer, specifying the position of that employer in the applicant's preference list
▲*A two-dimensional array indexed by an employer and a number <math>i</math> from 1 to <math>n</math>, naming the applicant who is each employer's {{nowrap|<math>i</math>th}} preference
Setting up these data structures takes <math>O(n^2)</math> time. With these structures it is possible to find an employer with an unfilled position, make an offer from that employer to their next applicant, determine whether the offer is accepted, and update all of the data structures to reflect the results of these steps, in constant time per offer. Once the algorithm terminates, the resulting matching can be read off from the array of employers for each applicant. There can be <math>O(n^2)</math> offers before each employer runs out of offers to make, so the total time is <math>O(n^2)</math>.{{r|kt}}
| |||