Если вы можете узнать количество студентов для каждого курса, то достаточно знать, есть ли курс с несколькими учениками> = N/2. В этом случае у вас есть сложность O(N) в худшем случае.
Если невозможно узнать количество студентов для каждого курса, вы можете использовать измененную оперативную сортировку. В каждом цикле вы выбираете случайного ученика и разделяете других учеников в одноклассниках и не одноклассниках. Если число одноклассников составляет> = N/2, вы останавливаетесь, потому что у вас есть ответ, иначе вы анализируете раздел, не относящийся к классу. Если число студентов в этом разделе составляет < N/2, вы останавливаетесь, потому что невозможно иметь количество одноклассников> = N/2, иначе вы выбираете другого ученика из раздела без классов и повторяете все, используя только не- -классные элементы.
Что мы берем из алгоритма быстрой сортировки, так это то, как мы разделяем студентов. Вышеприведенный алгоритм не имеет ничего общего с сортировкой.В псевдокоде это будет выглядеть примерно так (индексация массива начинается с 1 для наглядности):
Student[] students = all_students;
int startIndex = 1;
int endIndex = N; // number of students
int i;
while(startIndex <= N/2){
endIndex = N; // this index must point to the last position in each cycle
students.swap(startIndex, start index + random_int % (endIndex-startIndex));
for(i = startIndex + 1; i < endIndex;){
if(students[startIndex].isClassmatesWith(students[i])){
i++;
}else{
students.swap(i,endIndex);
endIndex--;
}
}
if(i-startIndex >= N/2){
return true;
}
startIndex = i;
}
return false;
Положение раздела перед началом алгоритма будет столь же просто, как:
| all_students_that_must_be_analyzed |
во время первого запуска набор студентов будет разделен следующим образом:
| classmates | to_be_analyzed | not_classmates |
и во время каждого запуска после него, набор студентов будет распределял следующим образом:
| to_ignore | classmates | to_be_analyzed | not_classmates |
В конце каждого запуска набор студентов будет разделена следующим образом:
| to_ignore | classmates | not_classmates |
На данный момент нам нужно проверить, если одноклассники раздел имеет более чем N/2 элемента. Если это имеет место, то мы имеем положительный результат, если нет, нам нужно проверить, содержит ли раздел not_classmates> = N/2 элемента. Если это так, то нам нужно продолжить другой прогон, иначе мы получим отрицательный результат.
Относительно сложности
Thinking более подробно на сложности выше алгоритма, существуют два основных фактора, которые влияют на его, которые являются:
- Число студентов на каждом курсе (нет необходимости знать это число для работы алгоритма).
- Среднее количество одноклассников, найденных на каждой итерации алгоритма.
Важной частью алгоритма является случайный выбор учащегося, подлежащего анализу.
В худшем случае будет, когда в каждом курсе будет 1 студент. В этом случае (по очевидным причинам я бы сказал) сложность была бы O(N^2). Если количество студентов для курсов меняется, то этого случая не произойдет.
Примером наихудшего сценария будет то, что у нас есть, скажем, 10 учеников, 10 курсов и 1 студент для каждого курса. Мы проверили бы 10 студентов в первый раз, 9 студентов во второй раз, 8 студентов в третий раз и так далее. Это приносит сложности O(N^2).
Лучший вариант сценария будет, когда первый студент, которого вы выбираете, находится в курсе с несколькими учениками> = N/2. В этом случае сложность будет O(N), потому что она остановится в первом прогоне.
Примером наилучшего сценария может быть, когда у нас 10 учеников, 5 (или более) из которых одноклассники, а в первом туре мы выбираем одного из этих 5 учеников. В этом случае мы будем проверять только одно время для одноклассников, находить 5 одноклассников и возвращать true.
средний сценарий - самая интересная часть (и более близкая к реальному сценарию).В этом случае есть некоторые вероятностные расчеты.
Прежде всего, шансы студента из определенного курса быть выбраны [number_of_students_in_the_course]/N. Это означает, что в первых тиражах более вероятно выбрать ученика со многими одноклассниками.
Рассматривая случай, когда среднее число одноклассников, найденных на каждой итерации, меньше числа N/2 (равно как и длина каждого раздела в среднем случае для quicksort). Предположим, что среднее количество одноклассников, найденное на каждой итерации, составляет 10% (количество, необходимое для удобства вычислений) оставшихся студентов М (которые не являются одноклассниками ранее выбранных студентов). В этом случае мы имели бы эти значения M для каждой итерации:
M1 = N - 0.1*N = 0.9*NM2 = M1 - 0.1*M1 = 0.9*M1 = 0.9*0.9*N = 0.81*NM3 = M2 - 0.1*M2 = 0.9*M2 = 0.9*0.81*N = 0.729*N и я бы округлить его 0.73*N для простоты расчетовM4 = 0.9*M3 = 0.9*0.73*N = 0.657*N ~= 0.66*NM5 = 0.9*M4 = 0.9*0.66*N = 0.594*N ~= 0.6*NM6 = 0.9*M5 = 0.9*0.6*N = 0.54*NM7 = 0.9*M6 = 0.9*0.54*N = 0.486*N ~= 0.49*N- Алгоритм останавливается, потому что у нас есть 49% оставшихся учеников, и среди них не может быть более N/2 одноклассников.
Очевидно, что в случае меньшего процента средних одноклассников число итераций будет больше, но в сочетании с первым фактом (учащиеся на курсах со многими учениками имеют более высокую вероятность попасть в ранние итераций), сложность будет стремиться к O(N), число итераций (во внешнем цикле в псевдокоде) будет (более или менее) постоянным и не будет зависеть от N.
Чтобы лучше объяснить этот сценарий, давайте работать с большими (но более реалистичными) числами и более чем одним распределением. Предположим, что у нас есть 100 учеников (число принято ради простоты вычислений) и что эти ученики распределяются среди курсов одним из следующих (гипотетических) способов (номера сортируются только для объяснения целей, они не нужны для алгоритма работы):
- 50, 30, 10, 5, 1, 1, 1, 1, 1
- 35, 27, 25, 10, 5, 1, 1, 1
- 11, 9, 9, 8, 7, 7, 5, 5, 5, 5, 5, 5, 5, 5, 5, 3, 1
числа, приведенные также (в данном конкретном случае) probab что ученик в курсе (не конкретный студент, только студент этого курса) выбирается в первом туре. Первый случай - это когда у нас есть курс с половиной студентов. Второй случай - это когда у нас нет курса с половиной студентов, но более 1 курса со многими учениками. Третий случай - это то, что мы имеем аналогичное распределение среди курсов.
В первом случае у нас будет 50% вероятность того, что учащийся 1-го курса будет выбран в первом туре, 30% вероятность того, что ученик второго курса будет выбран, вероятность 10% 3-й курс выбирается, 5% вероятность того, что ученик 4-го курса будет выбран, 1%, который будет выбран учеником 5-го курса, и так далее для 6-го, 7-го, 8-го и 9-го курсов.Вероятности выше для ученика 1-го случая, чтобы его выбрали рано, а в случае, если учащийся этого курса не будет выбран в первом туре, вероятности, которые он получает во втором прогоне, только увеличиваются. Например, предположим, что в первом туре выбран студент из второго курса. 30% студентов будут «удалены» (как в «больше не рассматривается»), а не будут проанализированы во втором прогоне. Во втором туре у нас осталось 70 учеников. Вероятность выбрать ученика из 1-го курса во втором прогоне составит 5/7, более 70%. Предположим, что - из-за неудачи - во 2-м туре выбирается ученик из 3-го курса. В третьем туре у нас осталось бы 60 учеников, и вероятность того, что студент первого курса будет выбран в третьем туре, составит 5/6 (более 80%). Я бы сказал, что мы можем считать, что наша неудача закончилась в 3-м туре, ученик из 1-го курса будет выбран, и метод возвращает true :)
Для 2-го и 3-го случаев я буду следить за вероятностями для каждый прогон, только для простоты вычислений.
Во втором случае у нас будет студент из 1-го курса, выбранного в 1-м туре. Поскольку число одноклассников не равно < = N/2, алгоритм продолжится со вторым прогоном. В конце 2-го тура мы бы «удалили» из ученика 35 + 27 = 62 ученика. В 3-м туре у нас осталось 38 студентов, и, будучи 38 < (N/2) = 50, вычисление останавливается и возвращает false.
То же самое происходит в третьем случае (в котором мы «удаляем» в среднем 10% оставшихся студентов за каждый прогон), но с большим количеством шагов.
Заключительные соображения
В любом случае, сложность алгоритма в худшем случае является O(N^2). В среднем сценарии в значительной степени зависит от вероятностей и, как правило, выбирает студентов из курсов со многими участниками. Такое поведение имеет тенденцию приводить к сложности до O(N), сложности, которые мы также имеем в сценарии наилучшего сценария .
Испытание алгоритма
Для того, чтобы проверить теоретическую сложность алгоритма я написал следующий код в C#:
public class Course
{
public int ID { get; set; }
public Course() : this(0) { }
public Course(int id)
{
ID = id;
}
public override bool Equals(object obj)
{
return (obj is Course) && this.Equals((Course)obj);
}
public bool Equals(Course other)
{
return ID == other.ID;
}
}
public class Student
{
public int ID { get; set; }
public Course Class { get; set; }
public Student(int id, Course course)
{
ID = id;
Class = course;
}
public Student(int id) : this(id, null) { }
public Student() : this(0) { }
public bool IsClassmatesWith(Student other)
{
return Class == other.Class;
}
public override bool Equals(object obj)
{
return (obj is Student) && this.Equals((Student)obj);
}
public bool Equals(Student other)
{
return ID == other.ID && Class == other.Class;
}
}
class Program
{
static int[] Sizes { get; set; }
static List<Student> Students { get; set; }
static List<Course> Courses { get; set; }
static void Initialize()
{
Sizes = new int[] { 2, 10, 100, 1000, 10000, 100000, 1000000 };
Students = new List<Student>();
Courses = new List<Course>();
}
static void PopulateCoursesList(int size)
{
for (int i = 1; i <= size; i++)
{
Courses.Add(new Course(i));
}
}
static void PopulateStudentsList(int size)
{
Random ran = new Random();
for (int i = 1; i <= size; i++)
{
Students.Add(new Student(i, Courses[ran.Next(Courses.Count)]));
}
}
static void Swap<T>(List<T> list, int i, int j)
{
if (i < list.Count && j < list.Count)
{
T temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
static bool AreHalfOfStudentsClassmates()
{
int startIndex = 0;
int endIndex;
int i;
int numberOfStudentsToConsider = (Students.Count + 1)/2;
Random ran = new Random();
while (startIndex <= numberOfStudentsToConsider)
{
endIndex = Students.Count - 1;
Swap(Students, startIndex, startIndex + ran.Next(endIndex + 1 - startIndex));
for (i = startIndex + 1; i <= endIndex;)
{
if (Students[startIndex].IsClassmatesWith(Students[i]))
{
i++;
}
else
{
Swap(Students, i, endIndex);
endIndex--;
}
}
if (i - startIndex + 1 >= numberOfStudentsToConsider)
{
return true;
}
startIndex = i;
}
return false;
}
static void Main(string[] args)
{
Initialize();
int studentsSize, coursesSize;
Stopwatch stopwatch = new Stopwatch();
TimeSpan duration;
bool result;
for (int i = 0; i < Sizes.Length; i++)
{
for (int j = 0; j < Sizes.Length; j++)
{
Courses.Clear();
Students.Clear();
studentsSize = Sizes[j];
coursesSize = Sizes[i];
PopulateCoursesList(coursesSize);
PopulateStudentsList(studentsSize);
Console.WriteLine("Test for {0} students and {1} courses.", studentsSize, coursesSize);
stopwatch.Start();
result = AreHalfOfStudentsClassmates();
stopwatch.Stop();
duration = stopwatch.Elapsed;
var studentsGrouping = Students.GroupBy(s => s.Class);
var classWithMoreThanHalfOfTheStudents = studentsGrouping.FirstOrDefault(g => g.Count() >= (studentsSize + 1)/2);
Console.WriteLine(result ? "At least half of the students are classmates." : "Less than half of the students are classmates");
if ((result && classWithMoreThanHalfOfTheStudents == null)
|| (!result && classWithMoreThanHalfOfTheStudents != null))
{
Console.WriteLine("There is something wrong with the result");
}
Console.WriteLine("Test duration: {0}", duration);
Console.WriteLine();
}
}
Console.ReadKey();
}
}
Время выполнения соответствует ожиданиям среднего сценария случая , Не стесняйтесь играть с кодом, вам просто нужно скопировать и вставить его, и он должен работать.
Не могли бы вы показать нам некоторые алгоритмы, которые вы пробовали до сих пор, чтобы мы могли видеть, что вы попытались это решить? –
Чтобы было ясно, нам нужно найти '> = N/2' или'> N/2'? Я смутно помню '> =' было намного проще в прошлый раз, когда я увидел эту проблему. –
> = N/2 ... нам нужно fild, если есть, наконец, N/2 одноклассников ... – DonTettino