مشهور‌ترین شخص

این سؤال یکی از سؤال‌هایی است که راه حل بدیهی از $O(n^2)$ دارد. اما یک راه حل هم با $O(n)$ دارد. ما در زیر به بررسی هر دو روش می‌پردازیم.

در یک مهمانی، $n$ نفر حضور دارند. بین هر دو نفر $A, B$ یک رابطه دوستی به این صورت برقرار است که یا $A$ نفر $B$ را می‌شناسد، یا بالعکس. می‌خواهیم با تعدادی پرسش، به صورت زیر، متوجه بشویم که آیا شخصی وجود دارد که همه را بشناسد یا خیر.
پرسش: آیا شخص $A$ شخص $B$ را می‌شناسد؟

یک روش بدیهی از $O(n^2)$ به این صورت است که به ازای هر شخص، در صورتی که این شخص همه افراد دیگر را می‌شناخت، شخص مورد نظر را به عنوان جواب سؤال در نظر بگیریم.
اما روشی با $O(n)$ ارائه می‌دهیم:
اگر شخص $A$ شخص $B$ را بشناسد، می‌توانیم مطمئن شویم که $A$ نمی‌تواند مشهور‌ترین فرد باشد. پس با یک پرسش به راحتی می‌توان یک کاندید را از کاندید‌های مشهور‌ترین فرد بودن، حذف کرد. حال عضو $n$ را در نظر نگیرید. با $n - 2$ پرسش، از بین $n - 1$ نفر باقی‌مانده، کاندید خود را انتخاب کنید. سپس با یک پرسش، بین کاندید خود و نفر $n$ ام، یک نفر را به عنوان کاندید نهایی انتخاب کنید. حال که کاندید نهایی را دارید، با $n - 1$ پرسش دیگر، بررسی کنید که آیا این کاندید مشهورترین شخص است یا خیر.

به وضوح پیچیدگی الگوریتم اول $O(n^2)$ و دومی $O(n)$ است.

celebrity.cpp

#include <iostream>
using namespace std;
int main() {
    int celeb = -1;
    for(int i=0;i<n;++i) {
        bool flag = true;
        for(int j=0;j<n;++j)
            if(i != j)
                if(ask(i, j) == false)     //imagine you have a finction ask, which tell you the answer for question ask(a, b). if b know a it returns true
                    flag = false;
        if(flag == true)
            celeb = i;
    }
 
    if(celeb != -1)
        cout << "We find it!! celebrity is: " << celeb + 1 << endl;
    else
        cout << "There is no celebrity :(" << endl;
 
    return 0;
}

celebrity_fast.cpp

#include <iostream>
using namespace std;
int main() {
    int celeb = 0;
    for(int i=1;i<n;++i)
        if(ask(celeb, i) == false)     //imagine you have a finction ask, which tell you the answer for question ask(a, b). if b know a it returns true
            celeb = i;
 
    bool flag = true;
    for(int i=0;i<n;++i)
        if(celeb != i && ask(celeb, i) == false)
            flag = false;
 
    if(flag == true)
        cout << "We find it!! celebrity is: " << celeb + 1 << endl;
    else
        cout << "There is no celebrity :(" << endl;
 
    return 0;
}

• http://www.geeksforgeeks.org/the-celebrity-problem/