Информатика | Іздеу және сұрыптау алгоритімдері
Барлық әдістерді статикалық және динамикалық деп қарастыруға болады. Массивтен статикалық әдіспен іздеу кезінде оның мәндері өзгермейді. Массивтен динамикалық әдіспен іздеу кезінде оның өлшемі өзгеруі мүмкін, себебі ол қайтадан сұрыпталады. Біз көбінде статикалық әдісті қолданамыз, үйткені мәтіндік редактордағы сөздерді өзгерте алмаймыз, ал динамикалық тәсіл ойын құрғанда пайдаланылады.
Іздеу әдістерін сондай-ақ нақты кілттерді пайдаланатын және туындаушы кілттерді пайдаланатын деп екіге бөледі. Бұл жағдайда кілт деп өзіміз іздеп отырған сөзді айтады. Мәтіндік редакторға қолданылатын кілт – туындаушы болып табылады, себебі ізделінетін массив алдын-ала алфавит бойынша сұрыпталған. Бұл рет іздеуді жеңілдету үшін пайдаланылады.
Кейбір кітаптарда бұл әдіс «экстраполяция әдісі» деп аталады. Экстарполяция – берілген интервалдан тыс бірнәрсені анықтау әдісі, ал интерпояция – сол интервал аралығына анықтау әдісі. Сондықтан да «экстраполяция әдісі» деп атау қате, үйткені ізделінетін сөзді шекарадан тыс аумақта іздеу мүмкін емес.бұл әдісті сипаттамас бұрын сізге ағылшын тіліндегі «treasure» сөзінің аудармасы қажет болды дейік. Яғни сіздің алдыңызда тапсырма – осы сөзді сөздіктен іздеу. Біздің келесі іс-әркеттеріміз қандай да бір іздеу алгоритмін құрумен жалғасады. Ізделінетін сөзді алфавит бойынша сұрыпталған массивтен іздейміз, ал керекті сөз бізге белгілі. Оны тез арада тауып алуға болады. Енді осы іздеуге толығымен тоқталайық. Бізге керекті сөз «т» әрпінен басталады, яғни алфавиттің екінші бөлігінде, немесе біз ол қандай орында тұрғанында шамамен есептеп ала аламыз. Яғни қанша дым жасауға болатынын анықтап аламыз. Егер ізделінетін массив үлкен болса осы әдіс арқылы оның шекрасын көрсетіп, тек осы аралықты ғана іздеуге болады. Ол үшін келесідей ек теңдік аламыз:
T1=M*N;
T2=2M*Log(2)N+N*Log(2)N;
N – массивтегі элементтердің саны.
M – рет іздеуге болады.
Тура ауытырудың алгоритмі жасайтын операция саны M*N-ге тең. Ал сұрыптауға кететін уақыт N*Log(2)N-ге тең, оған тағы 2M*Log(2)N дихотомия әдісін қосамыз. T1=T2 кезінде екі алгоритм де тиімді шекарада боламыз. ....
Іздеу әдістерін сондай-ақ нақты кілттерді пайдаланатын және туындаушы кілттерді пайдаланатын деп екіге бөледі. Бұл жағдайда кілт деп өзіміз іздеп отырған сөзді айтады. Мәтіндік редакторға қолданылатын кілт – туындаушы болып табылады, себебі ізделінетін массив алдын-ала алфавит бойынша сұрыпталған. Бұл рет іздеуді жеңілдету үшін пайдаланылады.
Кейбір кітаптарда бұл әдіс «экстраполяция әдісі» деп аталады. Экстарполяция – берілген интервалдан тыс бірнәрсені анықтау әдісі, ал интерпояция – сол интервал аралығына анықтау әдісі. Сондықтан да «экстраполяция әдісі» деп атау қате, үйткені ізделінетін сөзді шекарадан тыс аумақта іздеу мүмкін емес.бұл әдісті сипаттамас бұрын сізге ағылшын тіліндегі «treasure» сөзінің аудармасы қажет болды дейік. Яғни сіздің алдыңызда тапсырма – осы сөзді сөздіктен іздеу. Біздің келесі іс-әркеттеріміз қандай да бір іздеу алгоритмін құрумен жалғасады. Ізделінетін сөзді алфавит бойынша сұрыпталған массивтен іздейміз, ал керекті сөз бізге белгілі. Оны тез арада тауып алуға болады. Енді осы іздеуге толығымен тоқталайық. Бізге керекті сөз «т» әрпінен басталады, яғни алфавиттің екінші бөлігінде, немесе біз ол қандай орында тұрғанында шамамен есептеп ала аламыз. Яғни қанша дым жасауға болатынын анықтап аламыз. Егер ізделінетін массив үлкен болса осы әдіс арқылы оның шекрасын көрсетіп, тек осы аралықты ғана іздеуге болады. Ол үшін келесідей ек теңдік аламыз:
T1=M*N;
T2=2M*Log(2)N+N*Log(2)N;
N – массивтегі элементтердің саны.
M – рет іздеуге болады.
Тура ауытырудың алгоритмі жасайтын операция саны M*N-ге тең. Ал сұрыптауға кететін уақыт N*Log(2)N-ге тең, оған тағы 2M*Log(2)N дихотомия әдісін қосамыз. T1=T2 кезінде екі алгоритм де тиімді шекарада боламыз. ....
Рефераттар