Разлік часу складанасць алгарытмаў практычна

Я чытаў аб часовай складанасці толькі ў тэорыі .. Ці ёсць спосаб, каб вылічыць іх у праграме? Ня здагадкі, як «п» або што-небудзь, але фактычныя значэння ..

Напрыклад .. разлік часу складанасць сартавання зліццём і хуткай сартавання ..

Merge Sort= O(nlogn);// any case

Quick Sort= O(n^2);// worst case(when pivot is largest or smallest value)

ёсць велізарная розніца ў NlogN і п ^ 2 матэматычна ..

Так што я паспрабаваў гэта ў маёй праграме ..

main()
    {
       long t1=System.nanoTime();
      //code of program..
       long t2=System.nanoTime();
       time taken=t2-t1;
    }

Адказ я атрымаць для абодвух алгарытмаў, на самай справе для любога алгарытму я спрабаваў у асноўным 20.

Ці з'яўляецца System.nanoTime() не дастаткова, ці я павінен выкарыстоўваць павольную сістэму дакладнай? Ці ёсць іншы спосаб?

1
50-100 не з'яўляецца дастаткова вялікім выпрабаваннем для O (N ^ 2) ці O (п § п). Вы можаце паспрабаваць кучу значэнняў п - 10,100,1000,10000,100000,1000000. І, як правіла, вы хочаце запусціць яго некалькі разоў запар паміж запісам пачатку і канца, каб атрымаць больш дакладныя вынікі. І хутка сартаваць сярэдні выпадак O (п § п), такім чынам, вы можаце чакаць аналагічныя разы ад хуткай сартавання і зліцця сартавання, калі вы не адчуваць паталагічныя выпадкі.
дададзена аўтар Dukeling, крыніца
50-100 не з'яўляецца дастаткова вялікім выпрабаваннем для O (N ^ 2) ці O (п § п). Вы можаце паспрабаваць кучу значэнняў п - 10,100,1000,10000,100000,1000000. І, як правіла, вы хочаце запусціць яго некалькі разоў запар паміж запісам пачатку і канца, каб атрымаць больш дакладныя вынікі. І хутка сартаваць сярэдні выпадак O (п § п), такім чынам, вы можаце чакаць аналагічныя разы ад хуткай сартавання і зліцця сартавання, калі вы не адчуваць паталагічныя выпадкі.
дададзена аўтар Dukeling, крыніца
t1 знаходзіцца ў пачатку галоўнай() і t2 знаходзіцца ў канцы галоўнай ().
дададзена аўтар Shashank Raghunath, крыніца
t1 знаходзіцца ў пачатку галоўнай() і t2 знаходзіцца ў канцы галоўнай ().
дададзена аўтар Shashank Raghunath, крыніца
я спрабаваў з 50-100 значэнняў .. такі ж вынік.
дададзена аўтар Shashank Raghunath, крыніца
я спрабаваў з 50-100 значэнняў .. такі ж вынік.
дададзена аўтар Shashank Raghunath, крыніца
я спрабаваў з 50-100 значэнняў .. такі ж вынік.
дададзена аўтар Shashank Raghunath, крыніца
Колькі значэнняў Вы выкарыстоўвалі?
дададзена аўтар pad, крыніца
Колькі значэнняў Вы выкарыстоўвалі?
дададзена аўтар pad, крыніца
Колькі значэнняў Вы выкарыстоўвалі?
дададзена аўтар pad, крыніца

15 адказы

<�Р> Ці ёсць спосаб, каб вылічыць іх у праграме? Ня здагадкі, як «п» або што-небудзь, але фактычныя значэння.

Я думаю, вы зразумелі, што складанасць. Гэта не з'яўляецца каштоўнасцю. Гэта нават не шэраг значэнняў. Гэта <�ет> Формула . Калі вы пазбавіцеся ад N гэта не мае сэнсу, як меры складанасці (за выключэннем выпадку O (1) ... відавочна).


Ўстаноўка гэтага пытання на адным баку, было б тэарэтычна магчыма аўтаматызаваць пільны аналіз складанасці. Аднак гэта нялёгкая задача: аўтаматычнае доказ цяжка ... асабліва, калі няма чалавечых істот у цыкле, каб «кіраўніцтва» працэс. І Прыпыненне тэарэма <�ет> азначае , што не можа быць аўтаматызаваны тэарэма даказвае, што можа даказаць складанасць адвольнай праграмы. (Вядома, не можа быць складанасць выпрабавальнік, які працуе для ўсіх праграм, якія можа ці не можа спыніць ...)


Але ёсць адзін спосаб вылічыць меру прадукцыйнасці для праграмы з зададзеным наборам ўваходных дадзеных. Вы проста запусціце яго! І на самай справе, вы робіце серыю досведаў, прадукцыйнасць графікаў супраць некаторага памеру праблема вымярэння (г.зн. N ) ... і зрабіць абгрунтаванае меркаванне ў формуле, якая ставіцца да прадукцыйнасці і N мера. Ці вы маглі б паспрабаваць адпавядаць вымярэннях формулы.

Аднак ...

  • гэта толькі здагадка, і
  • гэты падыход не заўсёды будзе працаваць.

Напрыклад, калі вы спрабавалі гэта на класічным Quicksort, вы, хутчэй за ўсё, зрабіць выснову, што складанасць O (NlogN) і прапусціць важны нюанс, што ёсць «горшы выпадак», дзе O ( N ^ 2) . Іншы прыклад, дзе характарыстыкі назіранай прадукцыйнасці змяніць як памер праблемы становіцца вялікім.

Карацей кажучы, такі падыход нясе адказнасць, каб даць вам недакладныя адказы.

4
дададзена
<�Р> Ці ёсць спосаб, каб вылічыць іх у праграме? Ня здагадкі, як «п» або што-небудзь, але фактычныя значэння.

Я думаю, вы зразумелі, што складанасць. Гэта не з'яўляецца каштоўнасцю. Гэта нават не шэраг значэнняў. Гэта <�ет> Формула . Калі вы пазбавіцеся ад N гэта не мае сэнсу, як меры складанасці (за выключэннем выпадку O (1) ... відавочна).


Ўстаноўка гэтага пытання на адным баку, было б тэарэтычна магчыма аўтаматызаваць пільны аналіз складанасці. Аднак гэта нялёгкая задача: аўтаматычнае доказ цяжка ... асабліва, калі няма чалавечых істот у цыкле, каб «кіраўніцтва» працэс. І Прыпыненне тэарэма <�ет> азначае , што не можа быць аўтаматызаваны тэарэма даказвае, што можа даказаць складанасць адвольнай праграмы. (Вядома, не можа быць складанасць выпрабавальнік, які працуе для ўсіх праграм, якія можа ці не можа спыніць ...)


Але ёсць адзін спосаб вылічыць меру прадукцыйнасці для праграмы з зададзеным наборам ўваходных дадзеных. Вы проста запусціце яго! І на самай справе, вы робіце серыю досведаў, прадукцыйнасць графікаў супраць некаторага памеру праблема вымярэння (г.зн. N ) ... і зрабіць абгрунтаванае меркаванне ў формуле, якая ставіцца да прадукцыйнасці і N мера. Ці вы маглі б паспрабаваць адпавядаць вымярэннях формулы.

Аднак ...

  • гэта толькі здагадка, і
  • гэты падыход не заўсёды будзе працаваць.

Напрыклад, калі вы спрабавалі гэта на класічным Quicksort, вы, хутчэй за ўсё, зрабіць выснову, што складанасць O (NlogN) і прапусціць важны нюанс, што ёсць «горшы выпадак», дзе O ( N ^ 2) . Іншы прыклад, дзе характарыстыкі назіранай прадукцыйнасці змяніць як памер праблемы становіцца вялікім.

Карацей кажучы, такі падыход нясе адказнасць, каб даць вам недакладныя адказы.

4
дададзена

Ну, на практыцы з некаторымі дапушчэннямі па праграме, вы можаце быць у стане выканаць сваю праграму на вялікай колькасці тэсту (і вымераць час, неабходнае) і выкарыстоўваць інтэрпаляцыю для ацэнкі хуткасці росту і складанасці праграмы, а таксама выкарыстанне <�моцны> статыстычная праверка гіпотэз , каб паказаць верагоднасць вы правільна.

Аднак, гэтая рэч не можа быць зроблена ва ўсіх выпадках. На самай справе, вы нават не можаце мець алгарытм, які кажа для кожнай праграмы, калі яна збіраецца спыніць ці не (запусціць бясконцы цыкл). Гэта вядома як <�моцны> Праблема Прыпынкі , якая апынулася insolveable ,

2
дададзена

Ну, на практыцы з некаторымі дапушчэннямі па праграме, вы можаце быць у стане выканаць сваю праграму на вялікай колькасці тэсту (і вымераць час, неабходнае) і выкарыстоўваць інтэрпаляцыю для ацэнкі хуткасці росту і складанасці праграмы, а таксама выкарыстанне <�моцны> статыстычная праверка гіпотэз , каб паказаць верагоднасць вы правільна.

Аднак, гэтая рэч не можа быць зроблена ва ўсіх выпадках. На самай справе, вы нават не можаце мець алгарытм, які кажа для кожнай праграмы, калі яна збіраецца спыніць ці не (запусціць бясконцы цыкл). Гэта вядома як <�моцны> Праблема Прыпынкі , якая апынулася insolveable ,

2
дададзена

Microbenchmark, які вы напісалі няправільна. Калі вы хочаце, каб сабраць некаторыя часовыя паказчыкі вашага кода для далейшай аптымізацыі, JFF і г.д. выкарыстоўваць JMH . Гэта дапаможа вам шмат.

1
дададзена

Microbenchmark, які вы напісалі няправільна. Калі вы хочаце, каб сабраць некаторыя часовыя паказчыкі вашага кода для далейшай аптымізацыі, JFF і г.д. выкарыстоўваць JMH . Гэта дапаможа вам шмат.

1
дададзена

Калі мы кажам, што алгарытм дэманструе O (NlogN) складанасць, мы кажам, што <�ет> асімптатычнага верхняй мяжы для гэтага алгарытм O (NlogN) </код >. Гэта значыць, пры досыць вялікіх значэннях п , алгарытм паводзіць сябе як функцыі п увайсці п . Мы не кажам, што для п ўваходы, безумоўна, будзе п <�§ п/код> пакарання. Проста, што гэта набор вызначэння, што ваш алгарытм належыць.

Прымаючы інтэрвалы часу на вашай сістэме, вы фактычна падвяргаючы сябе розныя зменныя, якія ўдзельнічаюць у кампутарнай сістэме. Гэта значыць, вы маеце справу з сістэмай затрымкі, супраціў драты, хуткасць працэсара, выкарыстанне аператыўнай памяці ... і г.д. і да т.п. Усе гэтыя рэчы будуць мець адчувальнае ўплыў на ваш вынік. Менавіта таму мы выкарыстоўваем асимптотике , каб вылічыць часовую складанасць алгарытму.

1
дададзена

Калі мы кажам, што алгарытм дэманструе O (NlogN) складанасць, мы кажам, што <�ет> асімптатычнага верхняй мяжы для гэтага алгарытм O (NlogN) </код >. Гэта значыць, пры досыць вялікіх значэннях п , алгарытм паводзіць сябе як функцыі п увайсці п . Мы не кажам, што для п ўваходы, безумоўна, будзе п <�§ п/код> пакарання. Проста, што гэта набор вызначэння, што ваш алгарытм належыць.

Прымаючы інтэрвалы часу на вашай сістэме, вы фактычна падвяргаючы сябе розныя зменныя, якія ўдзельнічаюць у кампутарнай сістэме. Гэта значыць, вы маеце справу з сістэмай затрымкі, супраціў драты, хуткасць працэсара, выкарыстанне аператыўнай памяці ... і г.д. і да т.п. Усе гэтыя рэчы будуць мець адчувальнае ўплыў на ваш вынік. Менавіта таму мы выкарыстоўваем асимптотике , каб вылічыць часовую складанасць алгарытму.

1
дададзена

Калі мы кажам, што алгарытм дэманструе O (NlogN) складанасць, мы кажам, што <�ет> асімптатычнага верхняй мяжы для гэтага алгарытм O (NlogN) </код >. Гэта значыць, пры досыць вялікіх значэннях п , алгарытм паводзіць сябе як функцыі п увайсці п . Мы не кажам, што для п ўваходы, безумоўна, будзе п <�§ п/код> пакарання. Проста, што гэта набор вызначэння, што ваш алгарытм належыць.

Прымаючы інтэрвалы часу на вашай сістэме, вы фактычна падвяргаючы сябе розныя зменныя, якія ўдзельнічаюць у кампутарнай сістэме. Гэта значыць, вы маеце справу з сістэмай затрымкі, супраціў драты, хуткасць працэсара, выкарыстанне аператыўнай памяці ... і г.д. і да т.п. Усе гэтыя рэчы будуць мець адчувальнае ўплыў на ваш вынік. Менавіта таму мы выкарыстоўваем асимптотике , каб вылічыць часовую складанасць алгарытму.

1
дададзена

Мікра тэсты, як гэта па сваёй сутнасці недахопы, і вы ніколі не збіраецеся, каб атрымаць дакладныя паказанні бліскуча выкарыстоўваць іх - асабліва не ў дыяпазоне нанасекунд. JIT трэба час, каб «разагрэць» у код, на працягу якога ён будзе аптымізаваць вакол сябе, які менавіта код называецца.

Калі вы павінны ісці па гэтым шляху, то вам трэба вялікі тэставы набор для вашага алгарытму, які будзе прымаць секунд для запуску, а не нанасекунд, а пераважна «разагрэць» перыяд там, а таксама - то вы можаце ўбачыць некаторыя адрозненні, блізкія да таго, што вы чакалі. Вы ніколі не збіраецеся проста быць у стане прыняць гэтыя таймінгі, хоць і вылічыць часовую складанасць з іх непасрэдна - вы павінны былі б працаваць шмат выпадкаў з рознымі памерамі, а затым пабудаваць графік, каб час, неабходнае для кожнага памеру ўваходных дадзеных. Нават такі падыход не атрымае вам бліскуча дакладныя вынікі, але было б дастаткова, каб даць ўяўленне.

1
дададзена

Мікра тэсты, як гэта па сваёй сутнасці недахопы, і вы ніколі не збіраецеся, каб атрымаць дакладныя паказанні бліскуча выкарыстоўваць іх - асабліва не ў дыяпазоне нанасекунд. JIT трэба час, каб «разагрэць» у код, на працягу якога ён будзе аптымізаваць вакол сябе, які менавіта код называецца.

Калі вы павінны ісці па гэтым шляху, то вам трэба вялікі тэставы набор для вашага алгарытму, які будзе прымаць секунд для запуску, а не нанасекунд, а пераважна «разагрэць» перыяд там, а таксама - то вы можаце ўбачыць некаторыя адрозненні, блізкія да таго, што вы чакалі. Вы ніколі не збіраецеся проста быць у стане прыняць гэтыя таймінгі, хоць і вылічыць часовую складанасць з іх непасрэдна - вы павінны былі б працаваць шмат выпадкаў з рознымі памерамі, а затым пабудаваць графік, каб час, неабходнае для кожнага памеру ўваходных дадзеных. Нават такі падыход не атрымае вам бліскуча дакладныя вынікі, але было б дастаткова, каб даць ўяўленне.

1
дададзена

Адзін са спосабаў праверыць складанасць часу, каб запусціць абодва алгарытму, на розных памерах п і праверыць суадносіны паміж кожным запускам. З гэтага суадносін можна атрымаць часовую складанасць

For example
If time complexity is O(n) then the ratio will be linear

If time complexity is O(n^2) the ratio will be (n1/n2)^2
if time complexity is O(log(n)) the ratio will be log(n1)/log(n2)

1
дададзена

Адзін са спосабаў праверыць складанасць часу, каб запусціць абодва алгарытму, на розных памерах п і праверыць суадносіны паміж кожным запускам. З гэтага суадносін можна атрымаць часовую складанасць

For example
If time complexity is O(n) then the ratio will be linear

If time complexity is O(n^2) the ratio will be (n1/n2)^2
if time complexity is O(log(n)) the ratio will be log(n1)/log(n2)

1
дададзена

Ваша пытанне можа быць звязаны з Ці можа праграма разліку Складанасці алгарытм? і праграмы/алгарытм, каб знайсці часовую складанасць любой дадзенай праграмы , я думаю, што вы робіце праграму, дзе ў той час падліку або завес і паглядзець, калі яго укладзеным ці не, але я не разумею, як ты можна вылічыць складанасць для некаторых рэкурсіўныя функцыі.

1
дададзена

Ваша пытанне можа быць звязаны з Ці можа праграма разліку Складанасці алгарытм? і праграмы/алгарытм, каб знайсці часовую складанасць любой дадзенай праграмы , я думаю, што вы робіце праграму, дзе ў той час падліку або завес і паглядзець, калі яго укладзеным ці не, але я не разумею, як ты можна вылічыць складанасць для некаторых рэкурсіўныя функцыі.

1
дададзена