ntql l~ lmHtw~

DLOGTIME

mn wykybydy, lmwsw`@ lHr@
yftqr mHtw~ hdhh lmql@ l~ lstshhd bmSdr. fDlan, shm fy tTwyr hdhh lmql@ mn khll Df@ mSdr mwthwq bh. 'y m`lwmt Gyr mwthq@ ymkn ltshkyk bh wzlth. (ynyr 2022)

fy `lm lt`qyd DLOGTIME hw qsm lmsy'l lty ymkn Hlh bwsT@ al@ tywrnj ,dht wSwl `shwy'y ,Htmy@ Hyth 'n wqt Hsb al@ tywrnj hw ((O(log(n. hdh y`ny 'naW lal@ swf ttjhl lmudkhl m `d ((O(log(n mnh , wy`d hdh lqsm mn D`f lqsm lm`rwf@ dh nh SGr qsm lys bdyhy m`rwf km 'n kl lqsm l'khr~ tHwyh, 'Hd lmsy'l lty ymkn `tbrh tb`@ lhdh lqsm hy fHS Twl lmudkhl bms`d@ lbHth lthny'y , hnlk stkhdmt lhdh lqsm :

  1. lstkhdm l'wl hw t`ryf lt`qyd DLOGTIME-uniformty wldhy hw mhm fy t`qyd ldwy'r lbwlyny@ .
  2. t`ryf khtSr bHyth ykwn mly'm lkl lqsm lm`rwf@ mstGlyn fy hdh D`f DLOGTIME ,

fltkn f tHwyl@ (transformation) kthyr@ lHdwd mn lms'l@ X llms'l@ Y nqwl 'naW f hy tHwyl@ DLOGTIME dh llG@ {(x,i,c): lbt fy lmkn i fy (f(x hw c } tb`@ l-DLOGTIME

mrj`

[`dl]

nZr 'yD

[`dl]

hdhh bdhr@ mql@ `n lryDyt w mwDw` mt`lq bh bHj@ lltwsy`. fDlan shrk fy tHryrh.