Екі сұрыпталмаған жиынтықтың немесе тізімдердің қиылысы

Сізге $ L_1 $ және $ L_2 екі тізім берілді делік, олардың әрқайсысында кейбір $ S $ жиынтығынан жұптың әртүрлі элементтері бар.

Екі тізімнің $ L_1 \ cap L_2 $ қиылысуын есептеудің күрделілігі қандай?

Егер сізде $ S $ -да тапсырыс болса, сіз екі тізімді сұрыптап, содан соң $ O (n \ log n) $ күрделілігіне қол жеткізе отырып, сызықты уақыт аралығында қиылысатын есептеп, $ n = \ max (| L_1 |, | L_2 | ) $. Нақты мәселелер келесідей:

  • Сызықтық уақыт аралығында қиылысуды немесе $ O (n \ log n) $ қарағанда тезірек есептей аласыз ба?
  • $ S $ ішінде табиғи тапсырыс болмаса, сұрыптау алгоритмін пайдаланбай қандай күрделілікке қол жеткізе аласыз?

Екінші оқ нүктесі мүлдем анық емес. Түсінуді қалайтын нәрсе - тізімдерді (немесе олардың біреуін) сұрыптау сұраныстың сұрыпталуына тура келмейтініне қарамастан қажет.

4
Бұл қарапайым сызықты уақыт хешингке негізделген шешімге ие, ол зерттеуге қарағанда бакалавриаттың үй тапсырмасында болу үшін маған көбірек әсер етеді.
қосылды автор Marek Grzenkowicz, көзі
@DavidEppstein: Мен сізбен келісемін, мен cs.stackexchange туралы сұрағымды жіберген болар едім. Дегенмен, дәл айтылмағанымен, мен ең нашар детерминистикалық күрделілікке қызығамын. Hashing негізіндегі шешім осы параметрлерде сызықтық уақытқа жетуіне күмәнданамын.
қосылды автор Ozgur Ozcitak, көзі
Қатысты мәселе stackoverflow.com/q/8102478/58737
қосылды автор rossp, көзі
Сіз элементтерді қалай ұсынасыз? Егер олар ұзындығы еркін болуы мүмкін бит сызықтары болса, онда сіз, ең болмағанда, $ \ Omega (n) $ көп болуы мүмкін, себебі, сізде n ішіндегі көп полиномиальды жағдай болуы мүмкін. Егер элементтеріңіз шектеулі ұзын болса, сіз $ O (n) $ уақытында сұрыптауға болады. Егер сіз бір нәрсе туралы айтсаңыз, дәл солай?
қосылды автор pseudon, көзі
Мүмкін, сіз мұны білесіз бе, бірақ байланысты тақырып элементтің айырмашылық мәселесі деп аталады.
қосылды автор Saeed, көзі
@ ZsbánAmbrus, Біз әдеттегі RAM үлгісі туралы әңгімелеп береміз, сондықтан сіздің ойыңыз мұнда алаңдаушылық деп ойлаймын, қараңыз: . Мен Bruno-мен келісемін, мүмкін, бұл оңай, бірақ егер ол оңай болса, мен күмәнданамын. R-тізімдерін пайдаланудың кейбір жолдары салыстыру үлгісінде бұл $ o (n \ log n) $ ішінде жасалмайтынын және hashbased шешімі жаман нашар жағдайды (хэш - бұл теорияда біз күткендей, бірақ практикада шын мәнінде сиқырлы).
қосылды автор Saeed, көзі
Егер сіздің тізіміңіздің біреуі кексті хэшингке негізделген хэш-үстелге сақталған болса, онда сіз кукуша хэширлеуі ең нашар тұрақты іздеу уақытына кепілдік береді (бірақ кірулер тұрақты уақыт күтілуін талап етеді; сондықтан алдымен хэш-кестені құру үшін талап етілетін сызықтық уақытты елемеуге рұқсат етсеңіз деп сұрадым).
қосылды автор Massimo Cafaro, көзі

1 жауаптар

Алгебралық шешімдерде/есептеу ағашының модельдерінде сізде $ \ Omega (n \ log n) $ төменгі шегі бар, тіпті егер сіз тізімдеріңіздің біреуі $ 1 $ $ n $ $ n $ сандарының сұрыпталған тәртіпте бар екенін білсеңіз де, және екінші тізімнің бірінші орын ауыстыру екенін тексеру керек.

дәлелдеу (алгебралық есептеулер үшін ағаштар): $ (1,2, \ dots, n) $ айнымалы нүктелерінің координаты $ n! $ құрамдас бөліктері бар. Бен-Ор дәлелдегендей, кез-келген алгебралық биіктікке арналған $ h $ ағашының есептеуі үшін, $ R $ n $ тармағындағы нүктелер жиынтығы YES жапырақтарына көп $ 2 ^ h 3 ^ {n + h} $ құрамдастарына ие. $ H $ үшін шешіңіз.

Егер сіз теңдік сынақтарымен шектелетін болсаңыз, онда $ \ Omega (n ^ 2) $ төменгі шегі қарапайым қарсыластың дәлелінен туындайды.

8
қосылды