[Powered by Google Translate] તમે કદાચ સાંભળ્યું કર્યું છે લોકો ઝડપી કાર્યક્ષમ અલ્ગોરિધમનો વિશે વાત
તમારા ચોક્કસ કાર્ય ચલાવવા માટે,
પરંતુ ચોકકસ શું તે માટે ઝડપી કાર્યક્ષમ એલ્ગોરિધમ માટે અર્થ છે?
વેલ, તે વાસ્તવિક સમય માં એક માપ વિશે વાત છે,
સેકન્ડ માટે અથવા મિનિટ જેવા હોય છે.
આ કારણ છે કે કમ્પ્યુટર હાર્ડવેર
અને સોફ્ટવેર ભારે તફાવત હોય છે.
મારો કાર્યક્રમ તમારું કરતા ધીમી ગતિએ શકે છે,
કારણ કે હું તે જૂની કમ્પ્યુટર પર ચાલી રહ્યું છું,
અથવા કારણ કે હું એક ઑનલાઇન વિડિઓ ગેમ રમી શકાય થાય છે
તે જ સમયે, જે મારા બધા મેમરી hogging છે,
અથવા હું અલગ સોફ્ટવેર દ્વારા મારા કાર્યક્રમ ચલાવી રહ્યા હોય શકે છે
જે મશીન સાથે અલગ જોડાયેલો નીચા સ્તરે.
તે સફરજન અને નારંગી રંગ સરખામણી જેવું છે.
જસ્ટ કારણ કે મારા ધીમી કોમ્પ્યુટર સમય લે છે
કરતાં તમારામાં પાછળ એક જવાબ આપી
નથી તેનો અર્થ નથી કે તમે વધુ કાર્યક્ષમ અલ્ગોરિધમનો છે.
>> તેથી, આપણે સીધી કાર્યક્રમોની રનટાઇમને નથી તુલના કરી શકો છો
સેકન્ડ માટે અથવા મિનિટમાં,
અમે 2 વિવિધ ગાણિતીક નિયમો કેવી રીતે તુલના નથી
તેમના હાર્ડવેર અથવા સોફ્ટવેર પર્યાવરણની?
માટે ગાણિતિક કાર્યક્ષમતા માપવાની વધુ એકસમાન રીતે બનાવવા માટે,
કમ્પ્યુટર વૈજ્ઞાનિકો અને ગણિતશાસ્ત્રીઓ ઘડી છે
એક કાર્યક્રમના ઉપગીય જટિલતા માપવા માટે વિભાવનાઓ
અને સંકેત 'મોટા Ohnotation' કહેવાય
આ વર્ણન માટે.
આ ઔપચારિક વ્યાખ્યા એ છે કે એક કાર્ય એફ (x)
જી ક્રમ (x) પર ચાલે છે
જો અમુક કિંમત (x) અસ્તિત્વ ધરાવે છે, એક્સ ₀ અને
કેટલાક સતત, સી, જેના માટે
એફ (x) કરતાં ઓછા અથવા તેની બરાબર છે
કે સતત વખત જી (x)
બધા એક્સ ₀ કરતાં વધારે એક્સ માટે.
>> પરંતુ દૂર ઔપચારિક વ્યાખ્યા ન ભયભીત નથી શકાય છે.
આ શું ખરેખર નથી ઓછી સૈદ્ધાંતિક દ્રષ્ટિએ અર્થ આ છે?
વેલ, તે મૂળભૂત રીતે વિશ્લેષણ એક રીત છે
ઝડપી કેવી રીતે એક કાર્યક્રમ રનટાઈમ asymptotically વધે છે.
એટલે કે, તમારા ઇનપુટ્સ માપ અનંત તરફ વધે છે,
કહે છે, તમે 10 કદ ઝાકઝમાળ સરખામણીમાં 1000 માપ ઝાકઝમાળ સૉર્ટ કરી રહ્યા છો.
કેવી રીતે તમારી કાર્યક્રમની રનટાઈમ વધવા છે?
ઉદાહરણ તરીકે, અક્ષરો ગણતરી કલ્પના
એક શબ્દમાળા માં સરળ રસ્તો
સમગ્ર શબ્દમાળા મારફતે વૉકિંગ દ્વારા
પત્ર દ્વારા અક્ષર અને દરેક અક્ષર માટે એક કાઉન્ટર માટે 1 ઉમેરી રહ્યા છે.
આ અલ્ગોરિધમનો લિનીઅર સમય ચાલે કહેવાય છે
અક્ષરો સંખ્યા સંદર્ભમાં,
'એન' શબ્દમાળા છે.
ટૂંકમાં, તે ઓ (એન) માં ચાલે છે.
આ શા માટે છે?
વેલ, આ અભિગમ વાપરી રહ્યા હોય, સમય જરૂરી
સમગ્ર શબ્દમાળા પસાર
અક્ષરો સંખ્યા પ્રમાણમાં હોય છે.
શબ્દમાળા 20-અક્ષર અક્ષરો સંખ્યા ગણવા
છે બે વાર સુધી લેવા તે લે જઈને
એક શબ્દમાળા 10-અક્ષર અક્ષરો ગણતરી,
કારણ કે તમે બધા અક્ષરો જોવા હોય
અને દરેક અક્ષરની સમય સમાન રકમ જોવા લઈ જાય છે.
જેમ તમે અક્ષરો સંખ્યા વધી છે,
આ રનટાઈમ linearly ઇનપુટ લંબાઈ વધારો કરશે.
>> હવે, કલ્પના જો તમે કે રેખીય સમય નક્કી,
ઓ (એન), ફક્ત ઝડપી તમારા માટે પૂરતો ન હતો?
કદાચ તમે વિશાળ શબ્દમાળાઓ સ્ટોર કરી રહ્યાં છો,
અને તમે વધારાની સમય લેશે તે નથી પૂરુ કરી શકો છો
તેમના એક બાય એક ગણાય અક્ષરો તમામ પસાર થાય છે.
તેથી, તમે કંઇક અલગ કરવાનો પ્રયાસ કરવાનું નક્કી કર્યું.
જો તમે પહેલાથી જ અક્ષરો સંખ્યા સ્ટોર શું થશે
શબ્દમાળા માં, કહેવાય ચલ માં કહે છે, 'લેન'
પ્રારંભિક પર કાર્યક્રમ માં,
પહેલાં તમે પણ તમારા શબ્દમાળા માં ખૂબ પ્રથમ અક્ષર સંગ્રહિત?
પછી, તમારે હવે શું કરવું બહાર શબ્દમાળા લંબાઈ શોધી હો,
છે તપાસો ચલની કિંમત શું છે.
તમે પોતે જ બધી શબ્દમાળા જોવા ન હોવી જોઈએ,
અને લેન જેવી ચલની કિંમત ઍક્સેસ ગણવામાં આવે છે
એક asymptotically સતત સમય કામગીરી,
અથવા ઓ (1).
આ શા માટે છે? વેલ યાદ રાખો કે, ઉપગીય જટિલતા શું અર્થ થાય છે.
માપ તરીકે રનટાઈમ ફેરફાર કેવી રીતે કરે છે
તમારા ઇનપુટ્સ વધે?
>> કહો કે તમે કોઈ મોટા શબ્દમાળામાં અક્ષરો સંખ્યા વિચાર પ્રયાસ કરી રહ્યા હતા.
વેલ, તે તો કોઈ વાંધો આવશે મોટું તમે કેવી રીતે શબ્દમાળા બનાવવા માટે,
એક પણ મિલિયન અક્ષરો લાંબુ,
બધા તમે આ અભિગમ સાથે શબ્દમાળા લંબાઈ શોધવા કરો છો,
માટે બહાર ચલ લેન કિંમત વાંચી છે,
જે તમે પહેલાથી જ બનાવવામાં આવે છે.
ઇનપુટ લંબાઈ, છે, કે જે શબ્દમાળા તમે શોધવા માટે પ્રયાસ કરી રહ્યા છો તે લંબાઇ,
તમામ ઝડપી કેવી રીતે તમારા કાર્યક્રમ ચાલે અંતે અસર નથી.
તમારા કાર્યક્રમ આ ભાગ સમાન ઝડપી શબ્દમાળા એક અક્ષર પર ચલાવવા કરશે
અને શબ્દમાળા હજાર પાત્ર,
અને તેથી જ આ કાર્યક્રમ સતત સમય ચાલી રહેલ તરીકે ઉલ્લેખ કરવામાં આવશે
ઇનપુટ માપ આદર સાથે.
>> અલબત્ત, ત્યાં ખામી છે.
તમે તમારા કમ્પ્યુટર પર વધારે મેમરી જગ્યા બગાડવાની
આ ચલ સ્ટોર
અને વધારાના સમયમાં તે તમે લઈ જાય છે
માટે ચલની વાસ્તવિક સંગ્રહ કરવા માટે,
પરંતુ બિંદુ હજુ પણ છે,
બહાર શોધવા લાંબા કેવી રીતે તમારા શબ્દમાળા હતી
બધા અંતે શબ્દમાળા લંબાઈ પર આધાર રાખે છે કે નહીં.
તેથી, તે (1) O અથવા સતત સમય ચાલે છે.
આ ચોક્કસપણે અર્થ નથી
કે જે તમારી કોડ પગલું 1 ચાલે છે,
પરંતુ કોઇ બાબત કેટલા પગલાંઓ છે,
જો તે ઇનપુટ્સ માપ સાથે બદલાતું નથી,
તે હજુ asymptotically સતત જે અમે ઓ (1) તરીકે રજૂ કરે છે.
>> જેમ તમે કદાચ ધારી શકો,
ત્યાં ઘણા વિવિધ મોટું ઓ સાથે એલ્ગોરિધમ્સ માપવા રનટાઇમને છે.
ઓ (એન) ચોરસ એલ્ગોરિધમ્સ asymptotically ઓ એલ્ગોરિધમ્સ (એન) કરતાં ધીમી હોય છે.
કે છે, સંખ્યાબંધ તત્વો (એન) ઊગે છે,
છેવટે ઓ (એન) ચોરસ ગાણિતીક નિયમો વધુ સમય લેશે
કરતાં ઓ એલ્ગોરિધમ્સ (એન) ચલાવવા માટે.
આનો અર્થ એવો નથી ઓ એલ્ગોરિધમ્સ (એન) હંમેશા ઝડપી રન
ઓ (એન) ચોરસ ગાણિતીક નિયમો કરતાં, પણ એ જ પર્યાવરણમાં,
એ જ હાર્ડવેર પર.
કદાચ નાના ઇનપુટ માપો માટે,
આ (એન) ઓ ચોરસ અલ્ગોરિધમનો ખરેખર ઝડપથી કામ કરી શકે છે,
પરંતુ, છેવટે, ઇનપુટ કદ વધે છે
અનંત તરફ છે, ઓ (એન) ચોરસ માતાનો અલ્ગોરિધમનો રનટાઈમ
આખરે ઓ અલ્ગોરિધમનો (એન) ના રનટાઈમ ગ્રહણ કરશે.
ફક્ત કોઈપણ વર્ગાત્મક ગાણિતિક કાર્ય જેમ
છેવટે કોઇ રેખીય કાર્ય સ્થાન લઈ શક્યું હશે,
આ બોલ પર કોઈ દ્રવ્ય વડા કેટલા લાઇનર કાર્ય શરૂ સાથે બંધ થાય છે.
જો તમે માહિતી મોટી માત્રામાં સાથે કામ કરી રહ્યા છો,
ગાણિતીક નિયમો છે કે જે ઓ ચલાવવા (એન) ચોરસ સમય ખરેખર અંત તમારો કાર્યક્રમ ધીમી કરી શકે છે,
પરંતુ નાના કદના ઇનપુટ માટે,
તમે પણ કદાચ ન નોટિસ આવશે.
>> અન્ય અનંત સ્પર્શી જટિલતા છે,
લઘુગુણકીય સમય, ઓ (લોગ એન).
અલ્ગોરિધમ કે આ ઝડપથી ચાલે ઉદાહરણ
ક્લાસિક દ્વિસંગી શોધ એલ્ગોરિધમ છે,
તત્વોના પહેલાથી-છટણી સૂચિમાં એક તત્વ શોધવા માટે.
>> જો તમે જાણતા નથી દ્વિસંગી શોધ શું કરે છે,
હું તમારા માટે તે ખરેખર ઝડપથી સમજાવવું પડશે.
હવે કહો કે તમે 3 નંબર માટે શોધી રહ્યા છો
પૂર્ણાંકો આ એરે છે.
તે એરે મધ્યમાં તત્વ જુએ છે
અને પૂછે છે કે, "હું તત્વ કરતા વધારે માંગો છો છે, માટે, સમાન અથવા આ કરતાં ઓછું મળે છે?"
જો તે બરાબર હોય, તો પછી મહાન છે. તમે તત્વ મળી આવ્યું છે, અને તમે પૂર્ણ કરી રહ્યાં છો.
જો તે વધારે છે, તો પછી તમે તત્વ ખબર
માટે એરે જમણી બાજુ માં જ હોવી જોઇએ,
અને તમે માત્ર ભવિષ્યમાં કે જોવા કરી શકો છો,
અને જો તે નાની છે, તો પછી તમે જાણતા તે ડાબી બાજુ હોવી જોઇએ.
આ પ્રક્રિયા પછી એરે નાના કદના સાથે પુનરાવર્તન કરવામાં આવે છે
ત્યાં સુધી સાચી તત્વ જોવા મળે છે.
>> આ શક્તિશાળી અલ્ગોરિધમનો અડધા દરેક કામગીરી સાથે એરે કદ બનાવ્યો.
તેથી, થી 8 કદ એક છટણી એરે એક તત્વ શોધવા માટે,
વધુમાં વધુ, (8 ₂ લૉગ)
અથવા આ કામગીરી 3,
મધ્યમ તત્વ ચકાસણી, પછી અડધા માં એરે કાપવાની જરૂર પડશે,
જ્યારે 16 કદ ઝાકઝમાળ લે (16 ₂ લૉગ),
અથવા 4 કામગીરી.
કે માત્ર 1 એક એરે બમણી-કદ માટે વધુ કામગીરી છે.
એરે માપ ડબલિંગ
આ કોડ ફક્ત 1 ભાગ દ્વારા રનટાઈમ વધારે છે.
ફરીથી, આ યાદીમાં મધ્યમ તત્વ ચકાસણી, વિભાજન પછી.
તેથી, તે લઘુગુણકીય સમય કામ કહ્યું છે,
ઓ (લોગ એન).
પરંતુ તમે કહો, રાહ જુઓ,
નથી પર આધાર આ જ્યાં યાદીમાં તત્વ તમે શોધી રહ્યાં છો તે છે?
જો પ્રથમ તત્વ તમે જોવા જમણી એક બને છે?
પછી, તે માત્ર 1 કામગીરી લે છે,
કોઈ બાબત મોટી કેવી રીતે યાદી છે.
>> વેલ, કે શા માટે કમ્પ્યુટર વૈજ્ઞાનિકોનું શબ્દો વધુ હોય છે
અનંત સ્પર્શી જટિલતા કે જે શ્રેષ્ઠ કેસ પ્રતિબિંબિત માટે
અને સૌથી ખરાબ કેસ એક ગાણિતીક પ્રદર્શન.
વધુ યોગ્ય રીતે, ઉપલા અને નીચલા સીમાથી
આ રનટાઈમ છે.
દ્વિસંગી શોધ માટે શ્રેષ્ઠ કેસ, અમારા તત્વ છે
અધિકાર મધ્યમાં ત્યાં,
અને તમે તેને સતત સમય માટે,
કોઈ બાબત મોટી કેવી રીતે એરે બાકીના છે.
આ માટે વપરાય પ્રતીક Ω છે.
તેથી, આ ગણતરીઓ માટે Ω (1) ચલાવવા કહેવાય છે.
શ્રેષ્ઠ કિસ્સામાં, તેને તત્વ ઝડપથી શોધે છે,
કોઈ બાબત મોટી કેવી રીતે એરે છે,
પરંતુ ખરાબ કિસ્સામાં,
તે (લોગ એન) વિભાજીત તપાસમાં કરવા છે
એરે જમણી તત્વ શોધવા માટે બનાવવા માટે.
વર્સ્ટ કેસ ઉપર કિનારીઓ પર મોટા "O" ને કે તમે પહેલેથી જ ખબર સાથે ઓળખવામાં આવે છે.
તેથી, તે (લોગ એન) ઓ, પરંતુ Ω (1) છે.
>> એક રેખીય શોધ તેનાથી વિપરિત,
જેમાં તમે એરે દરેક તત્વ લઈ જવામાં
આ એક તમે કરવા માંગો છો શોધવા માટે,
Ω શ્રેષ્ઠ (1) પર છે.
ફરીથી, પ્રથમ તત્વ તમે કરવા માંગો છો.
તેથી, તે તો કોઈ વાંધો નથી મોટું કેવી રીતે એરે છે.
ખરાબમાં ખરાબ કિસ્સામાં, તે એરે છેલ્લા તત્વ છે.
તેથી, તમે એરે તમામ n તત્વોના લઈ જવામાં તેને શોધવા માટે હોય છે,
ગમે જો તમે 3 માટે શોધી રહ્યા હતા.
તેથી, તે ઓ સમય (એન) ચાલે છે
કારણ કે તે એરે માં સંખ્યાબંધ તત્વો માટે પ્રમાણસર છે.
>> એક વધુ ઉપયોગ પ્રતીક Θ છે.
આ એલ્ગોરિધમ્સ જ્યાં શ્રેષ્ઠ અને સૌથી ખરાબ કિસ્સાઓમાં વર્ણન માટે વાપરી શકાય છે
સમાન હોય છે.
આ શબ્દમાળા લંબાઈ એલ્ગોરિધમ્સ અમે વિશે અગાઉ વાત માં કેસ છે.
એટલે કે, જો અમે ચલ તે પહેલાં સ્ટોર
અમે શબ્દમાળા સ્ટોર છે અને તે સતત સમય પછી ઍક્સેસ કરો.
કોઈ બાબત નંબર શું
અમે તે ચલ માં સ્ટોર કરી રહ્યાં છો, તો અમે તેને જોવા મળશે.
શ્રેષ્ઠ કેસ છે, અમે તેને જોવા
અને શબ્દમાળા લંબાઈ શોધો.
(1) Ω અથવા શ્રેષ્ઠ કેસ સતત સમય રહે છે.
આ સૌથી ખરાબ કેસ છે,
અમે તેને જોવા અને શબ્દમાળા લંબાઈ શોધો.
તેથી, (1) O અથવા ખરાબ કિસ્સામાં સતત સમય.
તેથી, શ્રેષ્ઠ કેસ અને સૌથી ખરાબ કિસ્સાઓમાં કારણ કે સમાન હોય છે,
આ Θ સમય (1) ચલાવવા જણાવ્યું હતું શકાય છે.
>> સારાંશ, અમે કોડ કાર્યક્ષમતા અંગે કારણ સારી રીતો છે
સમય વાસ્તવિક દુનિયાની તેઓ માટે લઇ વિષે કશું જાણ્યા વગર,
જે બહાર પરિબળો ખૂબ જ અસરગ્રસ્ત છે,
અલગ હાર્ડવેર, સોફ્ટવેર સમાવેશ થાય છે,
અથવા તમારો કોડ ઓફ સ્પષ્ટીકરણો.
પણ, અમને સારી રીતે શું શું થશે તે વિશે કારણ માટે પરવાનગી આપે છે
જ્યારે ઇનપુટ્સ વધારો માપ.
>> જો તમે ઓ (એન) અલ્ગોરિધમનો ચોરસ માં ચલાવી રહ્યા છો,
અથવા ખરાબ છે, ઓ (2 ⁿ) એલ્ગોરિધમ,
સૌથી ઝડપથી વિકસતા પ્રકારો,
તમે ખરેખર આ મંદીના નોટિસ શરૂ કરી શકશો
જ્યારે તમે માહિતી મોટી માત્રામાં સાથે કામ કરવાનું શરૂ કરો.
>> કે ઉપગીય જટિલતા છે. આભાર.