EITC/IS/CCTF ਕੰਪਿਊਟੇਸ਼ਨਲ ਜਟਿਲਤਾ ਥਿਊਰੀ ਫੰਡਾਮੈਂਟਲਜ਼

ਕਿਉਂਕਿ ਇੱਕ ਐਲਗੋਰਿਦਮ ਨੂੰ ਚਲਾਉਣ ਲਈ ਲੋੜੀਂਦੇ ਸਰੋਤਾਂ ਦੀ ਮਾਤਰਾ ਇਨਪੁਟ ਦੇ ਆਕਾਰ ਦੇ ਨਾਲ ਬਦਲਦੀ ਹੈ, ਇਸ ਲਈ ਜਟਿਲਤਾ ਨੂੰ ਆਮ ਤੌਰ 'ਤੇ ਇੱਕ ਫੰਕਸ਼ਨ f(n) ਦੇ ਰੂਪ ਵਿੱਚ ਦਰਸਾਇਆ ਜਾਂਦਾ ਹੈ, ਜਿੱਥੇ n ਇਨਪੁਟ ਦਾ ਆਕਾਰ ਹੁੰਦਾ ਹੈ ਅਤੇ f(n) ਜਾਂ ਤਾਂ ਸਭ ਤੋਂ ਮਾੜੀ-ਕੇਸ ਗੁੰਝਲਤਾ ( ਸਾਈਜ਼ n ਦੇ ਸਾਰੇ ਇਨਪੁਟਸ ਲਈ ਲੋੜੀਂਦੇ ਸਰੋਤਾਂ ਦੀ ਅਧਿਕਤਮ ਮਾਤਰਾ) ਜਾਂ ਔਸਤ-ਕੇਸ ਦੀ ਗੁੰਝਲਤਾ (ਸਾਈਜ਼ n ਦੇ ਸਾਰੇ ਇਨਪੁਟਸ ਉੱਤੇ ਸਰੋਤਾਂ ਦੀ ਮਾਤਰਾ ਦੀ ਔਸਤ)। ਆਕਾਰ n ਦੇ ਇਨਪੁਟ 'ਤੇ ਲੋੜੀਂਦੇ ਐਲੀਮੈਂਟਰੀ ਓਪਰੇਸ਼ਨਾਂ ਦੀ ਸੰਖਿਆ ਨੂੰ ਆਮ ਤੌਰ 'ਤੇ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਵਜੋਂ ਦਰਸਾਇਆ ਜਾਂਦਾ ਹੈ, ਜਿੱਥੇ ਮੰਨਿਆ ਜਾਂਦਾ ਹੈ ਕਿ ਐਲੀਮੈਂਟਰੀ ਓਪਰੇਸ਼ਨਾਂ ਨੂੰ ਕਿਸੇ ਖਾਸ ਕੰਪਿਊਟਰ 'ਤੇ ਲਗਾਤਾਰ ਸਮਾਂ ਲੱਗਦਾ ਹੈ ਅਤੇ ਕਿਸੇ ਵੱਖਰੀ ਮਸ਼ੀਨ 'ਤੇ ਚੱਲਣ 'ਤੇ ਸਿਰਫ ਇੱਕ ਸਥਿਰ ਕਾਰਕ ਦੁਆਰਾ ਬਦਲਿਆ ਜਾਂਦਾ ਹੈ। ਆਕਾਰ n ਦੇ ਇੱਕ ਇੰਪੁੱਟ ਉੱਤੇ ਇੱਕ ਐਲਗੋਰਿਦਮ ਦੁਆਰਾ ਲੋੜੀਂਦੀ ਮੈਮੋਰੀ ਦੀ ਮਾਤਰਾ ਨੂੰ ਸਪੇਸ ਜਟਿਲਤਾ ਕਿਹਾ ਜਾਂਦਾ ਹੈ।

ਸਮਾਂ ਸਭ ਤੋਂ ਵੱਧ ਮੰਨਿਆ ਜਾਂਦਾ ਸਰੋਤ ਹੈ। ਜਦੋਂ ਸ਼ਬਦ "ਜਟਿਲਤਾ" ਨੂੰ ਕੁਆਲੀਫਾਇਰ ਤੋਂ ਬਿਨਾਂ ਵਰਤਿਆ ਜਾਂਦਾ ਹੈ, ਤਾਂ ਇਹ ਆਮ ਤੌਰ 'ਤੇ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ।

ਸਮੇਂ ਦੀਆਂ ਪਰੰਪਰਾਗਤ ਇਕਾਈਆਂ (ਸਕਿੰਟ, ਮਿੰਟ, ਅਤੇ ਹੋਰ) ਜਟਿਲਤਾ ਸਿਧਾਂਤ ਵਿੱਚ ਕੰਮ ਨਹੀਂ ਕੀਤੀਆਂ ਜਾਂਦੀਆਂ ਕਿਉਂਕਿ ਉਹ ਚੁਣੇ ਗਏ ਕੰਪਿਊਟਰ ਅਤੇ ਤਕਨਾਲੋਜੀ ਦੀ ਤਰੱਕੀ 'ਤੇ ਬਹੁਤ ਜ਼ਿਆਦਾ ਨਿਰਭਰ ਹਨ। ਉਦਾਹਰਨ ਲਈ, ਅੱਜ ਇੱਕ ਕੰਪਿਊਟਰ 1960 ਦੇ ਦਹਾਕੇ ਤੋਂ ਇੱਕ ਕੰਪਿਊਟਰ ਨਾਲੋਂ ਕਾਫ਼ੀ ਤੇਜ਼ੀ ਨਾਲ ਇੱਕ ਐਲਗੋਰਿਦਮ ਨੂੰ ਚਲਾ ਸਕਦਾ ਹੈ, ਫਿਰ ਵੀ, ਇਹ ਐਲਗੋਰਿਦਮ ਦੀ ਅੰਦਰੂਨੀ ਗੁਣਵੱਤਾ ਦੀ ਬਜਾਏ ਕੰਪਿਊਟਰ ਹਾਰਡਵੇਅਰ ਵਿੱਚ ਤਕਨੀਕੀ ਸਫਲਤਾਵਾਂ ਦੇ ਕਾਰਨ ਹੈ। ਜਟਿਲਤਾ ਸਿਧਾਂਤ ਦਾ ਟੀਚਾ ਐਲਗੋਰਿਦਮ ਦੀਆਂ ਅੰਦਰੂਨੀ ਸਮੇਂ ਦੀਆਂ ਲੋੜਾਂ, ਜਾਂ ਬੁਨਿਆਦੀ ਸਮਾਂ ਸੀਮਾਵਾਂ ਨੂੰ ਮਾਪਣਾ ਹੈ ਜੋ ਇੱਕ ਐਲਗੋਰਿਦਮ ਕਿਸੇ ਵੀ ਕੰਪਿਊਟਰ 'ਤੇ ਲਾਗੂ ਕਰੇਗਾ। ਇਹ ਗਣਨਾ ਦੇ ਦੌਰਾਨ ਕਿੰਨੇ ਬੁਨਿਆਦੀ ਓਪਰੇਸ਼ਨ ਕੀਤੇ ਗਏ ਹਨ ਦੀ ਗਿਣਤੀ ਕਰਕੇ ਪੂਰਾ ਕੀਤਾ ਜਾਂਦਾ ਹੈ। ਇਹਨਾਂ ਪ੍ਰਕਿਰਿਆਵਾਂ ਨੂੰ ਆਮ ਤੌਰ 'ਤੇ ਕਦਮਾਂ ਵਜੋਂ ਜਾਣਿਆ ਜਾਂਦਾ ਹੈ ਕਿਉਂਕਿ ਇਹਨਾਂ ਨੂੰ ਇੱਕ ਖਾਸ ਮਸ਼ੀਨ 'ਤੇ ਲਗਾਤਾਰ ਸਮਾਂ ਲੈਣ ਲਈ ਮੰਨਿਆ ਜਾਂਦਾ ਹੈ (ਭਾਵ, ਉਹ ਇਨਪੁਟ ਦੀ ਮਾਤਰਾ ਦੁਆਰਾ ਪ੍ਰਭਾਵਿਤ ਨਹੀਂ ਹੁੰਦੇ ਹਨ)।

ਇੱਕ ਹੋਰ ਮਹੱਤਵਪੂਰਨ ਸਰੋਤ ਐਲਗੋਰਿਦਮ ਕਰਨ ਲਈ ਲੋੜੀਂਦੀ ਕੰਪਿਊਟਰ ਮੈਮੋਰੀ ਦੀ ਮਾਤਰਾ ਹੈ।

ਇੱਕ ਹੋਰ ਅਕਸਰ ਵਰਤਿਆ ਜਾਣ ਵਾਲਾ ਸਰੋਤ ਅੰਕਗਣਿਤ ਕਾਰਜਾਂ ਦੀ ਮਾਤਰਾ ਹੈ। ਇਸ ਦ੍ਰਿਸ਼ਟੀਕੋਣ ਵਿੱਚ, ਸ਼ਬਦ "ਅੰਕਗਣਿਤ ਜਟਿਲਤਾ" ਵਰਤਿਆ ਜਾਂਦਾ ਹੈ। ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਆਮ ਤੌਰ 'ਤੇ ਇੱਕ ਸਥਿਰ ਕਾਰਕ ਦੁਆਰਾ ਅੰਕਗਣਿਤ ਦੀ ਗੁੰਝਲਤਾ ਦਾ ਉਤਪਾਦ ਹੁੰਦੀ ਹੈ ਜੇਕਰ ਗਣਨਾ ਦੌਰਾਨ ਹੋਣ ਵਾਲੀਆਂ ਸੰਖਿਆਵਾਂ ਦੀ ਬਾਈਨਰੀ ਪ੍ਰਤੀਨਿਧਤਾ ਦੇ ਆਕਾਰ 'ਤੇ ਇੱਕ ਉਪਰਲੀ ਰੁਕਾਵਟ ਜਾਣੀ ਜਾਂਦੀ ਹੈ।

ਇੱਕ ਗਣਨਾ ਦੌਰਾਨ ਵਰਤੇ ਗਏ ਪੂਰਨ ਅੰਕਾਂ ਦਾ ਆਕਾਰ ਬਹੁਤ ਸਾਰੇ ਤਰੀਕਿਆਂ ਲਈ ਸੀਮਤ ਨਹੀਂ ਹੈ, ਅਤੇ ਇਹ ਮੰਨਣਾ ਵਾਸਤਵਿਕ ਨਹੀਂ ਹੈ ਕਿ ਅੰਕਗਣਿਤ ਦੀਆਂ ਕਾਰਵਾਈਆਂ ਲਈ ਇੱਕ ਨਿਸ਼ਚਿਤ ਸਮੇਂ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ। ਨਤੀਜੇ ਵਜੋਂ, ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ, ਜਿਸ ਨੂੰ ਬਿੱਟ ਜਟਿਲਤਾ ਵੀ ਕਿਹਾ ਜਾਂਦਾ ਹੈ, ਗਣਿਤ ਦੀ ਗੁੰਝਲਤਾ ਨਾਲੋਂ ਕਾਫ਼ੀ ਜ਼ਿਆਦਾ ਹੋ ਸਕਦੀ ਹੈ। ਇੱਕ nn ਪੂਰਨ ਅੰਕ ਮੈਟ੍ਰਿਕਸ ਦੇ ਨਿਰਧਾਰਕ ਦੀ ਗਣਨਾ ਕਰਨ ਦੀ ਗਣਿਤ ਦੀ ਮੁਸ਼ਕਲ, ਉਦਾਹਰਨ ਲਈ, ਮਿਆਰੀ ਤਕਨੀਕਾਂ (ਗੌਸੀਅਨ ਐਲੀਮੀਨੇਸ਼ਨ) ਲਈ O(n^3) ਹੈ। ਕਿਉਂਕਿ ਗਣਨਾ ਦੌਰਾਨ ਗੁਣਾਂਕ ਦਾ ਆਕਾਰ ਤੇਜ਼ੀ ਨਾਲ ਫੈਲ ਸਕਦਾ ਹੈ, ਉਸੇ ਢੰਗਾਂ ਦੀ ਬਿੱਟ ਗੁੰਝਲਤਾ n ਵਿੱਚ ਘਾਤਕ ਹੈ। ਜੇਕਰ ਇਹਨਾਂ ਤਕਨੀਕਾਂ ਨੂੰ ਬਹੁ-ਮਾਡਿਊਲਰ ਅੰਕਗਣਿਤ ਦੇ ਨਾਲ ਜੋੜ ਕੇ ਵਰਤਿਆ ਜਾਂਦਾ ਹੈ, ਤਾਂ ਬਿੱਟ ਜਟਿਲਤਾ ਨੂੰ O(n^4) ਤੱਕ ਘਟਾਇਆ ਜਾ ਸਕਦਾ ਹੈ।

ਬਿੱਟ ਜਟਿਲਤਾ, ਰਸਮੀ ਸ਼ਬਦਾਂ ਵਿੱਚ, ਇੱਕ ਐਲਗੋਰਿਦਮ ਨੂੰ ਚਲਾਉਣ ਲਈ ਲੋੜੀਂਦੇ ਬਿੱਟਾਂ 'ਤੇ ਕਾਰਵਾਈਆਂ ਦੀ ਸੰਖਿਆ ਨੂੰ ਦਰਸਾਉਂਦੀ ਹੈ। ਇਹ ਜ਼ਿਆਦਾਤਰ ਗਣਨਾ ਪੈਰਾਡਾਈਮਜ਼ ਵਿੱਚ ਇੱਕ ਸਥਿਰ ਕਾਰਕ ਤੱਕ ਅਸਥਾਈ ਜਟਿਲਤਾ ਦੇ ਬਰਾਬਰ ਹੈ। ਕੰਪਿਊਟਰ ਦੁਆਰਾ ਲੋੜੀਂਦੇ ਮਸ਼ੀਨ ਸ਼ਬਦਾਂ 'ਤੇ ਕਾਰਵਾਈਆਂ ਦੀ ਗਿਣਤੀ ਬਿੱਟ ਜਟਿਲਤਾ ਦੇ ਅਨੁਪਾਤੀ ਹੈ। ਗਣਨਾ ਦੇ ਯਥਾਰਥਵਾਦੀ ਮਾਡਲਾਂ ਲਈ, ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਅਤੇ ਬਿੱਟ ਗੁੰਝਲਤਾ ਇਸ ਤਰ੍ਹਾਂ ਸਮਾਨ ਹਨ।

ਉਹ ਸਰੋਤ ਜੋ ਅਕਸਰ ਛਾਂਟੀ ਅਤੇ ਖੋਜ ਵਿੱਚ ਮੰਨਿਆ ਜਾਂਦਾ ਹੈ ਉਹ ਹੈ ਐਂਟਰੀਆਂ ਦੀ ਤੁਲਨਾ ਦੀ ਮਾਤਰਾ। ਜੇਕਰ ਡੇਟਾ ਚੰਗੀ ਤਰ੍ਹਾਂ ਵਿਵਸਥਿਤ ਕੀਤਾ ਗਿਆ ਹੈ, ਤਾਂ ਇਹ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਦਾ ਇੱਕ ਚੰਗਾ ਸੂਚਕ ਹੈ।

ਸਾਰੇ ਸੰਭਾਵੀ ਇਨਪੁਟਸ 'ਤੇ, ਇੱਕ ਐਲਗੋਰਿਦਮ ਵਿੱਚ ਕਦਮਾਂ ਦੀ ਗਿਣਤੀ ਕਰਨਾ ਅਸੰਭਵ ਹੈ। ਕਿਉਂਕਿ ਇੱਕ ਇੰਪੁੱਟ ਦੀ ਗੁੰਝਲਤਾ ਇਸਦੇ ਆਕਾਰ ਦੇ ਨਾਲ ਵੱਧਦੀ ਹੈ, ਇਸਨੂੰ ਆਮ ਤੌਰ 'ਤੇ ਇਨਪੁਟ ਦੇ ਆਕਾਰ n (ਬਿੱਟਾਂ ਵਿੱਚ) ਦੇ ਇੱਕ ਫੰਕਸ਼ਨ ਵਜੋਂ ਦਰਸਾਇਆ ਜਾਂਦਾ ਹੈ, ਅਤੇ ਇਸਲਈ ਜਟਿਲਤਾ n ਦਾ ਇੱਕ ਫੰਕਸ਼ਨ ਹੈ। ਇੱਕੋ-ਆਕਾਰ ਦੇ ਇਨਪੁਟਸ ਲਈ, ਹਾਲਾਂਕਿ, ਇੱਕ ਐਲਗੋਰਿਦਮ ਦੀ ਗੁੰਝਲਤਾ ਕਾਫ਼ੀ ਬਦਲ ਸਕਦੀ ਹੈ। ਨਤੀਜੇ ਵਜੋਂ, ਕਈ ਤਰ੍ਹਾਂ ਦੇ ਗੁੰਝਲਦਾਰ ਫੰਕਸ਼ਨ ਨਿਯਮਿਤ ਤੌਰ 'ਤੇ ਲਗਾਏ ਜਾਂਦੇ ਹਨ।

ਸਭ ਤੋਂ ਮਾੜੀ-ਕੇਸ ਗੁੰਝਲਤਾ ਸਾਰੇ ਆਕਾਰ n ਇਨਪੁਟਸ ਲਈ ਸਾਰੀਆਂ ਜਟਿਲਤਾ ਦਾ ਜੋੜ ਹੈ, ਜਦੋਂ ਕਿ ਔਸਤ-ਕੇਸ ਜਟਿਲਤਾ ਸਾਰੇ ਆਕਾਰ n ਇਨਪੁਟਸ ਲਈ ਸਾਰੀਆਂ ਜਟਿਲਤਾ ਦਾ ਜੋੜ ਹੈ (ਇਸਦਾ ਅਰਥ ਹੈ, ਕਿਉਂਕਿ ਦਿੱਤੇ ਆਕਾਰ ਦੇ ਸੰਭਾਵਿਤ ਇਨਪੁਟਸ ਦੀ ਸੰਖਿਆ ਸੀਮਿਤ)। ਜਦੋਂ "ਜਟਿਲਤਾ" ਸ਼ਬਦ ਨੂੰ ਹੋਰ ਪਰਿਭਾਸ਼ਿਤ ਕੀਤੇ ਬਿਨਾਂ ਵਰਤਿਆ ਜਾਂਦਾ ਹੈ, ਤਾਂ ਸਭ ਤੋਂ ਮਾੜੇ-ਕੇਸ ਸਮੇਂ ਦੀ ਜਟਿਲਤਾ ਨੂੰ ਧਿਆਨ ਵਿੱਚ ਰੱਖਿਆ ਜਾਂਦਾ ਹੈ।

ਸਭ ਤੋਂ ਮਾੜੇ-ਕੇਸ ਅਤੇ ਔਸਤ-ਕੇਸ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਸਹੀ ਢੰਗ ਨਾਲ ਗਣਨਾ ਕਰਨਾ ਬਹੁਤ ਮੁਸ਼ਕਲ ਹੈ। ਇਸ ਤੋਂ ਇਲਾਵਾ, ਇਹਨਾਂ ਸਹੀ ਮੁੱਲਾਂ ਵਿੱਚ ਬਹੁਤ ਘੱਟ ਵਿਹਾਰਕ ਉਪਯੋਗ ਹੈ ਕਿਉਂਕਿ ਮਸ਼ੀਨ ਜਾਂ ਗਣਨਾ ਦੇ ਪੈਰਾਡਾਈਮ ਵਿੱਚ ਕੋਈ ਵੀ ਤਬਦੀਲੀ ਗੁੰਝਲਦਾਰਤਾ ਨੂੰ ਥੋੜ੍ਹਾ ਵੱਖਰਾ ਕਰੇਗੀ। ਇਸ ਤੋਂ ਇਲਾਵਾ, n ਦੇ ਛੋਟੇ ਮੁੱਲਾਂ ਲਈ ਸਰੋਤ ਦੀ ਵਰਤੋਂ ਮਹੱਤਵਪੂਰਨ ਨਹੀਂ ਹੈ, ਇਸ ਲਈ ਲਾਗੂ ਕਰਨ ਦੀ ਸੌਖ ਅਕਸਰ ਛੋਟੇ n ਲਈ ਘੱਟ ਗੁੰਝਲਤਾ ਨਾਲੋਂ ਵਧੇਰੇ ਆਕਰਸ਼ਕ ਹੁੰਦੀ ਹੈ।

ਇਹਨਾਂ ਕਾਰਨਾਂ ਕਰਕੇ, ਉੱਚ n ਲਈ ਜਟਿਲਤਾ ਦੇ ਵਿਵਹਾਰ ਵੱਲ ਸਭ ਤੋਂ ਵੱਧ ਧਿਆਨ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ, ਯਾਨੀ ਕਿ, ਜਿਵੇਂ ਕਿ n ਅਨੰਤਤਾ ਦੇ ਨੇੜੇ ਪਹੁੰਚਦਾ ਹੈ, ਇਸਦਾ ਅਸੈਂਪਟੋਟਿਕ ਵਿਵਹਾਰ। ਨਤੀਜੇ ਵਜੋਂ, ਗੁੰਝਲਤਾ ਨੂੰ ਦਰਸਾਉਣ ਲਈ ਆਮ ਤੌਰ 'ਤੇ ਵੱਡੇ O ਸੰਕੇਤ ਦੀ ਵਰਤੋਂ ਕੀਤੀ ਜਾਂਦੀ ਹੈ।

ਕੰਪਿਊਟੇਸ਼ਨਲ ਮਾਡਲ

ਇੱਕ ਗਣਨਾ ਮਾਡਲ ਦੀ ਚੋਣ, ਜਿਸ ਵਿੱਚ ਜ਼ਰੂਰੀ ਓਪਰੇਸ਼ਨਾਂ ਨੂੰ ਨਿਰਧਾਰਤ ਕਰਨਾ ਸ਼ਾਮਲ ਹੁੰਦਾ ਹੈ ਜੋ ਸਮੇਂ ਦੀ ਇਕਾਈ ਵਿੱਚ ਕੀਤੇ ਜਾਂਦੇ ਹਨ, ਗੁੰਝਲਤਾ ਨੂੰ ਨਿਰਧਾਰਤ ਕਰਨ ਵਿੱਚ ਮਹੱਤਵਪੂਰਨ ਹੁੰਦਾ ਹੈ। ਇਸ ਨੂੰ ਕਈ ਵਾਰ ਮਲਟੀਟੇਪ ਟਿਊਰਿੰਗ ਮਸ਼ੀਨ ਕਿਹਾ ਜਾਂਦਾ ਹੈ ਜਦੋਂ ਗਣਨਾ ਪੈਰਾਡਾਈਮ ਦਾ ਵਿਸ਼ੇਸ਼ ਤੌਰ 'ਤੇ ਵਰਣਨ ਨਹੀਂ ਕੀਤਾ ਜਾਂਦਾ ਹੈ।

ਗਣਨਾ ਦਾ ਇੱਕ ਨਿਰਣਾਇਕ ਮਾਡਲ ਉਹ ਹੁੰਦਾ ਹੈ ਜਿਸ ਵਿੱਚ ਮਸ਼ੀਨ ਦੀਆਂ ਅਗਲੀਆਂ ਅਵਸਥਾਵਾਂ ਅਤੇ ਕੀਤੇ ਜਾਣ ਵਾਲੇ ਕਾਰਜ ਪੂਰੀ ਤਰ੍ਹਾਂ ਪਿਛਲੀ ਅਵਸਥਾ ਦੁਆਰਾ ਪਰਿਭਾਸ਼ਿਤ ਹੁੰਦੇ ਹਨ। ਆਵਰਤੀ ਫੰਕਸ਼ਨ, ਲਾਂਬਡਾ ਕੈਲਕੂਲਸ, ਅਤੇ ਟਿਊਰਿੰਗ ਮਸ਼ੀਨਾਂ ਪਹਿਲੇ ਨਿਰਣਾਇਕ ਮਾਡਲ ਸਨ। ਰੈਂਡਮ-ਐਕਸੈਸ ਮਸ਼ੀਨਾਂ (ਰੈਮ-ਮਸ਼ੀਨਾਂ ਵਜੋਂ ਵੀ ਜਾਣੀਆਂ ਜਾਂਦੀਆਂ ਹਨ) ਅਸਲ-ਸੰਸਾਰ ਕੰਪਿਊਟਰਾਂ ਦੀ ਨਕਲ ਕਰਨ ਲਈ ਇੱਕ ਪ੍ਰਸਿੱਧ ਪੈਰਾਡਾਈਮ ਹਨ।

ਜਦੋਂ ਗਣਨਾ ਮਾਡਲ ਨੂੰ ਪਰਿਭਾਸ਼ਿਤ ਨਹੀਂ ਕੀਤਾ ਜਾਂਦਾ ਹੈ, ਤਾਂ ਇੱਕ ਮਲਟੀਟੇਪ ਟਿਊਰਿੰਗ ਮਸ਼ੀਨ ਨੂੰ ਆਮ ਤੌਰ 'ਤੇ ਮੰਨਿਆ ਜਾਂਦਾ ਹੈ। ਮਲਟੀਟੇਪ ਟਿਊਰਿੰਗ ਮਸ਼ੀਨਾਂ 'ਤੇ, ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਜ਼ਿਆਦਾਤਰ ਐਲਗੋਰਿਦਮ ਲਈ RAM ਮਸ਼ੀਨਾਂ ਵਾਂਗ ਹੀ ਹੁੰਦੀ ਹੈ, ਹਾਲਾਂਕਿ ਇਸ ਸਮਾਨਤਾ ਨੂੰ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਮੈਮੋਰੀ ਵਿੱਚ ਡੇਟਾ ਨੂੰ ਕਿਵੇਂ ਸਟੋਰ ਕੀਤਾ ਜਾਂਦਾ ਹੈ ਇਸ ਵੱਲ ਕਾਫ਼ੀ ਧਿਆਨ ਦੇਣ ਦੀ ਲੋੜ ਹੋ ਸਕਦੀ ਹੈ।

ਕੰਪਿਊਟਿੰਗ ਦੇ ਇੱਕ ਗੈਰ-ਨਿਰਧਾਰਤ ਮਾਡਲ ਵਿੱਚ ਗਣਨਾ ਦੇ ਕੁਝ ਪੜਾਵਾਂ 'ਤੇ ਕਈ ਵਿਕਲਪ ਕੀਤੇ ਜਾ ਸਕਦੇ ਹਨ, ਜਿਵੇਂ ਕਿ ਗੈਰ-ਨਿਰਧਾਰਤ ਟਿਊਰਿੰਗ ਮਸ਼ੀਨਾਂ। ਜਟਿਲਤਾ ਥਿਊਰੀ ਵਿੱਚ, ਸਾਰੇ ਵਿਵਹਾਰਕ ਵਿਕਲਪਾਂ ਨੂੰ ਇੱਕੋ ਸਮੇਂ 'ਤੇ ਵਿਚਾਰਿਆ ਜਾਂਦਾ ਹੈ, ਅਤੇ ਗੈਰ-ਨਿਰਧਾਰਤ ਸਮੇਂ ਦੀ ਗੁੰਝਲਤਾ ਉਸ ਸਮੇਂ ਦੀ ਮਾਤਰਾ ਹੁੰਦੀ ਹੈ ਜਦੋਂ ਸਭ ਤੋਂ ਵਧੀਆ ਵਿਕਲਪ ਹਮੇਸ਼ਾ ਕੀਤੇ ਜਾਂਦੇ ਹਨ। ਇਸ ਨੂੰ ਹੋਰ ਤਰੀਕੇ ਨਾਲ ਕਹਿਣ ਲਈ, ਗਣਨਾ ਲੋੜ ਅਨੁਸਾਰ ਬਹੁਤ ਸਾਰੇ (ਇੱਕੋ ਜਿਹੇ) ਪ੍ਰੋਸੈਸਰਾਂ 'ਤੇ ਇੱਕੋ ਸਮੇਂ ਕੀਤੀ ਜਾਂਦੀ ਹੈ, ਅਤੇ ਗੈਰ-ਨਿਰਧਾਰਤ ਗਣਨਾ ਸਮਾਂ ਗਣਨਾ ਨੂੰ ਪੂਰਾ ਕਰਨ ਲਈ ਪਹਿਲੇ ਪ੍ਰੋਸੈਸਰ ਦੁਆਰਾ ਲਿਆ ਗਿਆ ਸਮਾਂ ਹੈ। ਇਸ ਸਮਾਨਤਾ ਨੂੰ ਕੁਆਂਟਮ ਕੰਪਿਊਟਿੰਗ ਵਿੱਚ ਵਿਸ਼ੇਸ਼ ਕੁਆਂਟਮ ਐਲਗੋਰਿਦਮ ਚਲਾਉਣ ਵੇਲੇ ਸੁਪਰਪੋਜ਼ਡ ਉਲਝੀਆਂ ਅਵਸਥਾਵਾਂ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਵਰਤਿਆ ਜਾ ਸਕਦਾ ਹੈ, ਜਿਵੇਂ ਕਿ ਉਦਾਹਰਨ ਲਈ ਛੋਟੇ ਪੂਰਨ ਅੰਕਾਂ ਦਾ ਸ਼ੌਰ ਦਾ ਗੁਣਨਕੀਕਰਨ।

ਭਾਵੇਂ ਅਜਿਹਾ ਗਣਨਾ ਮਾਡਲ ਵਰਤਮਾਨ ਵਿੱਚ ਵਿਹਾਰਕ ਨਹੀਂ ਹੈ, ਇਸਦੀ ਸਿਧਾਂਤਕ ਮਹੱਤਤਾ ਹੈ, ਖਾਸ ਤੌਰ 'ਤੇ P = NP ਸਮੱਸਿਆ ਦੇ ਸਬੰਧ ਵਿੱਚ, ਜੋ ਇਹ ਪੁੱਛਦੀ ਹੈ ਕਿ ਕੀ "ਬਹੁਪੰਥੀ ਸਮਾਂ" ਅਤੇ "ਗੈਰ-ਨਿਰਧਾਰਤ ਬਹੁਪਦਵੀ ਸਮਾਂ" ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਪੈਦਾ ਕੀਤੀਆਂ ਜਟਿਲਤਾ ਸ਼੍ਰੇਣੀਆਂ ਘੱਟੋ-ਘੱਟ ਉਪਰਲੇ ਹਨ। ਸੀਮਾਵਾਂ ਇੱਕੋ ਜਿਹੀਆਂ ਹਨ। ਇੱਕ ਨਿਰਣਾਇਕ ਕੰਪਿਊਟਰ 'ਤੇ, ਇੱਕ NP-ਐਲਗੋਰਿਦਮ ਦੀ ਨਕਲ ਕਰਨ ਲਈ "ਘਾਤਕ ਸਮਾਂ" ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ। ਜੇਕਰ ਇੱਕ ਕਾਰਜ ਨੂੰ ਇੱਕ ਗੈਰ-ਨਿਰਧਾਰਤ ਪ੍ਰਣਾਲੀ 'ਤੇ ਬਹੁਪਦ ਦੇ ਸਮੇਂ ਵਿੱਚ ਹੱਲ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ, ਤਾਂ ਇਹ NP ਮੁਸ਼ਕਲ ਸ਼੍ਰੇਣੀ ਨਾਲ ਸਬੰਧਤ ਹੈ। ਜੇਕਰ ਕੋਈ ਮੁੱਦਾ NP ਵਿੱਚ ਹੈ ਅਤੇ ਕਿਸੇ ਹੋਰ NP ਸਮੱਸਿਆ ਨਾਲੋਂ ਆਸਾਨ ਨਹੀਂ ਹੈ, ਤਾਂ ਇਸਨੂੰ NP-ਪੂਰਾ ਕਿਹਾ ਜਾਂਦਾ ਹੈ। ਨੈਪਸੈਕ ਸਮੱਸਿਆ, ਯਾਤਰਾ ਕਰਨ ਵਾਲੇ ਸੇਲਜ਼ਮੈਨ ਦੀ ਸਮੱਸਿਆ, ਅਤੇ ਬੁਲੀਅਨ ਸੰਤੁਸ਼ਟੀ ਦੀ ਸਮੱਸਿਆ ਇਹ ਸਾਰੀਆਂ NP-ਸੰਪੂਰਨ ਸੰਯੁਕਤ ਸਮੱਸਿਆਵਾਂ ਹਨ। ਸਭ ਤੋਂ ਮਸ਼ਹੂਰ ਐਲਗੋਰਿਦਮ ਵਿੱਚ ਇਹਨਾਂ ਸਾਰੀਆਂ ਸਮੱਸਿਆਵਾਂ ਲਈ ਘਾਤਕ ਜਟਿਲਤਾ ਹੈ। ਜੇਕਰ ਇਹਨਾਂ ਵਿੱਚੋਂ ਕਿਸੇ ਵੀ ਮੁੱਦੇ ਨੂੰ ਇੱਕ ਨਿਰਧਾਰਕ ਮਸ਼ੀਨ 'ਤੇ ਬਹੁਪਦ ਦੇ ਸਮੇਂ ਵਿੱਚ ਹੱਲ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ, ਤਾਂ ਸਾਰੀਆਂ NP ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਬਹੁਪਦ ਦੇ ਸਮੇਂ ਵਿੱਚ ਵੀ ਹੱਲ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ, ਅਤੇ P = NP ਸਥਾਪਤ ਕੀਤਾ ਜਾਵੇਗਾ। 2017 ਤੱਕ, ਇਹ ਵਿਆਪਕ ਤੌਰ 'ਤੇ ਮੰਨਿਆ ਜਾਂਦਾ ਹੈ ਕਿ P NP, ਇਹ ਦਰਸਾਉਂਦਾ ਹੈ ਕਿ NP ਸਮੱਸਿਆਵਾਂ ਦੀਆਂ ਸਭ ਤੋਂ ਭੈੜੀਆਂ ਸਥਿਤੀਆਂ ਨੂੰ ਹੱਲ ਕਰਨਾ ਬੁਨਿਆਦੀ ਤੌਰ 'ਤੇ ਮੁਸ਼ਕਲ ਹੈ, ਭਾਵ, ਦਿਲਚਸਪ ਇਨਪੁਟ ਲੰਬਾਈ ਦਿੱਤੇ ਗਏ ਕਿਸੇ ਵੀ ਸੰਭਵ ਸਮਾਂ ਮਿਆਦ (ਦਹਾਕਿਆਂ) ਤੋਂ ਬਹੁਤ ਜ਼ਿਆਦਾ ਸਮਾਂ ਲੱਗਦਾ ਹੈ।

ਸਮਾਨਾਂਤਰ ਅਤੇ ਵਿਤਰਿਤ ਕੰਪਿਊਟਿੰਗ

ਸਮਾਨਾਂਤਰ ਅਤੇ ਵਿਤਰਿਤ ਕੰਪਿਊਟਿੰਗ ਵਿੱਚ ਕਈ ਪ੍ਰੋਸੈਸਰਾਂ ਵਿੱਚ ਪ੍ਰੋਸੈਸਿੰਗ ਨੂੰ ਵੰਡਣਾ ਸ਼ਾਮਲ ਹੁੰਦਾ ਹੈ ਜੋ ਸਾਰੇ ਇੱਕੋ ਸਮੇਂ 'ਤੇ ਕੰਮ ਕਰਦੇ ਹਨ। ਵੱਖ-ਵੱਖ ਮਾਡਲਾਂ ਵਿਚਕਾਰ ਬੁਨਿਆਦੀ ਅੰਤਰ ਪ੍ਰੋਸੈਸਰਾਂ ਵਿਚਕਾਰ ਡੇਟਾ ਭੇਜਣ ਦਾ ਤਰੀਕਾ ਹੈ। ਸਮਾਨਾਂਤਰ ਕੰਪਿਊਟਿੰਗ ਵਿੱਚ ਪ੍ਰੋਸੈਸਰਾਂ ਵਿਚਕਾਰ ਡਾਟਾ ਸੰਚਾਰਨ ਆਮ ਤੌਰ 'ਤੇ ਬਹੁਤ ਤੇਜ਼ ਹੁੰਦਾ ਹੈ, ਜਦੋਂ ਕਿ ਡਿਸਟਰੀਬਿਊਟਡ ਕੰਪਿਊਟਿੰਗ ਵਿੱਚ ਪ੍ਰੋਸੈਸਰਾਂ ਵਿਚਕਾਰ ਡੇਟਾ ਟ੍ਰਾਂਸਫਰ ਇੱਕ ਨੈੱਟਵਰਕ ਵਿੱਚ ਕੀਤਾ ਜਾਂਦਾ ਹੈ ਅਤੇ ਇਸ ਤਰ੍ਹਾਂ ਕਾਫ਼ੀ ਹੌਲੀ ਹੁੰਦਾ ਹੈ।

N ਪ੍ਰੋਸੈਸਰਾਂ 'ਤੇ ਇੱਕ ਗਣਨਾ ਘੱਟੋ-ਘੱਟ N ਦੁਆਰਾ ਇੱਕ ਸਿੰਗਲ ਪ੍ਰੋਸੈਸਰ 'ਤੇ ਲੱਗਣ ਵਾਲੇ ਸਮੇਂ ਦਾ ਹਿੱਸਾ ਲੈਂਦੀ ਹੈ। ਅਸਲੀਅਤ ਵਿੱਚ, ਕਿਉਂਕਿ ਕੁਝ ਉਪ-ਕਾਰਜਾਂ ਨੂੰ ਸਮਾਨਾਂਤਰ ਨਹੀਂ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ ਅਤੇ ਕੁਝ ਪ੍ਰੋਸੈਸਰਾਂ ਨੂੰ ਕਿਸੇ ਹੋਰ ਪ੍ਰੋਸੈਸਰ ਤੋਂ ਨਤੀਜੇ ਦੀ ਉਡੀਕ ਕਰਨੀ ਪੈ ਸਕਦੀ ਹੈ, ਇਹ ਸਿਧਾਂਤਕ ਤੌਰ 'ਤੇ ਆਦਰਸ਼ ਸੀਮਾ ਕਦੇ ਵੀ ਪ੍ਰਾਪਤ ਨਹੀਂ ਹੋਵੇਗੀ।

ਇਸ ਤਰ੍ਹਾਂ ਮੁੱਖ ਜਟਿਲਤਾ ਦਾ ਮੁੱਦਾ ਐਲਗੋਰਿਦਮ ਨੂੰ ਵਿਕਸਤ ਕਰਨਾ ਹੈ ਤਾਂ ਜੋ ਪ੍ਰੋਸੈਸਰਾਂ ਦੀ ਗਿਣਤੀ ਦੁਆਰਾ ਕੰਪਿਊਟਿੰਗ ਸਮੇਂ ਦਾ ਉਤਪਾਦ ਇੱਕ ਸਿੰਗਲ ਪ੍ਰੋਸੈਸਰ 'ਤੇ ਇੱਕੋ ਗਣਨਾ ਕਰਨ ਲਈ ਲੋੜੀਂਦੇ ਸਮੇਂ ਦੇ ਜਿੰਨਾ ਸੰਭਵ ਹੋ ਸਕੇ ਨੇੜੇ ਹੋਵੇ।

ਕੁਆਂਟਮ ਗਣਨਾ

ਇੱਕ ਕੁਆਂਟਮ ਕੰਪਿਊਟਰ ਇੱਕ ਕੁਆਂਟਮ ਮਕੈਨਿਕਸ-ਆਧਾਰਿਤ ਗਣਨਾ ਮਾਡਲ ਵਾਲਾ ਇੱਕ ਕੰਪਿਊਟਰ ਹੁੰਦਾ ਹੈ। ਚਰਚ-ਟਿਊਰਿੰਗ ਥੀਸਿਸ ਕੁਆਂਟਮ ਕੰਪਿਊਟਰਾਂ ਲਈ ਸਹੀ ਹੈ, ਜਿਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਕੋਈ ਵੀ ਮੁੱਦਾ ਜਿਸ ਨੂੰ ਇੱਕ ਕੁਆਂਟਮ ਕੰਪਿਊਟਰ ਹੱਲ ਕਰ ਸਕਦਾ ਹੈ ਇੱਕ ਟਿਊਰਿੰਗ ਮਸ਼ੀਨ ਦੁਆਰਾ ਵੀ ਹੱਲ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ। ਹਾਲਾਂਕਿ, ਕੁਝ ਕਾਰਜ ਸਿਧਾਂਤਕ ਤੌਰ 'ਤੇ ਇੱਕ ਮਹੱਤਵਪੂਰਨ ਤੌਰ 'ਤੇ ਘੱਟ ਟੈਂਪੋਰਲ ਜਟਿਲਤਾ ਵਾਲੇ ਕਲਾਸੀਕਲ ਕੰਪਿਊਟਰ ਦੀ ਬਜਾਏ ਕੁਆਂਟਮ ਕੰਪਿਊਟਰ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਹੱਲ ਕੀਤੇ ਜਾ ਸਕਦੇ ਹਨ। ਫਿਲਹਾਲ, ਇਹ ਸਖਤੀ ਨਾਲ ਸਿਧਾਂਤਕ ਹੈ, ਕਿਉਂਕਿ ਕੋਈ ਨਹੀਂ ਜਾਣਦਾ ਕਿ ਵਿਹਾਰਕ ਕੁਆਂਟਮ ਕੰਪਿਊਟਰ ਕਿਵੇਂ ਵਿਕਸਿਤ ਕਰਨਾ ਹੈ।

ਕੁਆਂਟਮ ਜਟਿਲਤਾ ਸਿਧਾਂਤ ਵੱਖ-ਵੱਖ ਕਿਸਮਾਂ ਦੇ ਮੁੱਦਿਆਂ ਦੀ ਜਾਂਚ ਕਰਨ ਲਈ ਬਣਾਇਆ ਗਿਆ ਸੀ ਜੋ ਕੁਆਂਟਮ ਕੰਪਿਊਟਰਾਂ ਦੁਆਰਾ ਹੱਲ ਕੀਤੇ ਜਾ ਸਕਦੇ ਹਨ। ਇਸਦੀ ਵਰਤੋਂ ਪੋਸਟ-ਕੁਆਂਟਮ ਕ੍ਰਿਪਟੋਗ੍ਰਾਫੀ ਵਿੱਚ ਕੀਤੀ ਜਾਂਦੀ ਹੈ, ਜੋ ਕਿ ਕ੍ਰਿਪਟੋਗ੍ਰਾਫਿਕ ਪ੍ਰੋਟੋਕੋਲ ਬਣਾਉਣ ਦੀ ਪ੍ਰਕਿਰਿਆ ਹੈ ਜੋ ਕੁਆਂਟਮ ਕੰਪਿਊਟਰ ਹਮਲਿਆਂ ਪ੍ਰਤੀ ਰੋਧਕ ਹੁੰਦੇ ਹਨ।

ਸਮੱਸਿਆ ਦੀ ਜਟਿਲਤਾ (ਹੇਠਲੀਆਂ ਸੀਮਾਵਾਂ)

ਐਲਗੋਰਿਦਮ ਦੀਆਂ ਜਟਿਲਤਾਵਾਂ ਜੋ ਸਮੱਸਿਆ ਨੂੰ ਹੱਲ ਕਰ ਸਕਦੀਆਂ ਹਨ, ਅਣਡਿੱਠੀਆਂ ਤਕਨੀਕਾਂ ਸਮੇਤ, ਸਮੱਸਿਆ ਦੀ ਜਟਿਲਤਾ ਹੈ। ਨਤੀਜੇ ਵਜੋਂ, ਕਿਸੇ ਸਮੱਸਿਆ ਦੀ ਗੁੰਝਲਤਾ ਕਿਸੇ ਵੀ ਐਲਗੋਰਿਦਮ ਦੀ ਜਟਿਲਤਾ ਦੇ ਬਰਾਬਰ ਹੁੰਦੀ ਹੈ ਜੋ ਇਸਨੂੰ ਹੱਲ ਕਰਦੀ ਹੈ।

ਨਤੀਜੇ ਵਜੋਂ, ਵੱਡੇ O ਨੋਟੇਸ਼ਨ ਵਿੱਚ ਦਿੱਤੀ ਗਈ ਕੋਈ ਵੀ ਗੁੰਝਲਤਾ ਐਲਗੋਰਿਦਮ ਅਤੇ ਇਸ ਨਾਲ ਜੁੜੀ ਸਮੱਸਿਆ ਦੋਵਾਂ ਦੀ ਜਟਿਲਤਾ ਨੂੰ ਦਰਸਾਉਂਦੀ ਹੈ।

ਦੂਜੇ ਪਾਸੇ, ਮੁੱਦੇ ਦੀ ਗੁੰਝਲਤਾ 'ਤੇ ਗੈਰ-ਮਾਮੂਲੀ ਹੇਠਲੇ ਸੀਮਾਵਾਂ ਨੂੰ ਪ੍ਰਾਪਤ ਕਰਨਾ ਅਕਸਰ ਮੁਸ਼ਕਲ ਹੁੰਦਾ ਹੈ, ਅਤੇ ਅਜਿਹਾ ਕਰਨ ਲਈ ਕੁਝ ਰਣਨੀਤੀਆਂ ਹੁੰਦੀਆਂ ਹਨ।

ਜ਼ਿਆਦਾਤਰ ਮੁੱਦਿਆਂ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ, ਸਾਰੇ ਇਨਪੁਟ ਡੇਟਾ ਨੂੰ ਪੜ੍ਹਿਆ ਜਾਣਾ ਚਾਹੀਦਾ ਹੈ, ਜਿਸ ਵਿੱਚ ਡੇਟਾ ਦੀ ਤੀਬਰਤਾ ਦੇ ਅਨੁਪਾਤ ਵਿੱਚ ਸਮਾਂ ਲੱਗਦਾ ਹੈ। ਨਤੀਜੇ ਵਜੋਂ, ਅਜਿਹੀਆਂ ਸਮੱਸਿਆਵਾਂ ਵਿੱਚ ਘੱਟੋ-ਘੱਟ ਰੇਖਿਕ ਗੁੰਝਲਤਾ ਹੁੰਦੀ ਹੈ, ਜਾਂ, ਵੱਡੇ ਓਮੇਗਾ ਸੰਕੇਤ ਵਿੱਚ, Ω(n) ਦੀ ਗੁੰਝਲਤਾ ਹੁੰਦੀ ਹੈ।

ਕੁਝ ਸਮੱਸਿਆਵਾਂ, ਜਿਵੇਂ ਕਿ ਕੰਪਿਊਟਰ ਅਲਜਬਰੇ ਅਤੇ ਕੰਪਿਊਟੇਸ਼ਨਲ ਅਲਜਬਰੇਕ ਜਿਓਮੈਟਰੀ ਵਿੱਚ, ਬਹੁਤ ਵੱਡੇ ਹੱਲ ਹਨ। ਕਿਉਂਕਿ ਆਉਟਪੁੱਟ ਨੂੰ ਲਿਖਿਆ ਜਾਣਾ ਚਾਹੀਦਾ ਹੈ, ਗੁੰਝਲਤਾ ਆਉਟਪੁੱਟ ਦੇ ਵੱਧ ਤੋਂ ਵੱਧ ਆਕਾਰ ਦੁਆਰਾ ਸੀਮਤ ਹੈ।

ਇੱਕ ਲੜੀਬੱਧ ਐਲਗੋਰਿਦਮ ਲਈ ਲੋੜੀਂਦੀਆਂ ਤੁਲਨਾਵਾਂ ਦੀ ਸੰਖਿਆ ਵਿੱਚ Ω(nlogn) ਦੀ ਇੱਕ ਗੈਰ-ਰੇਖਿਕ ਨੀਵੀਂ ਸੀਮਾ ਹੁੰਦੀ ਹੈ। ਨਤੀਜੇ ਵਜੋਂ, ਸਭ ਤੋਂ ਵਧੀਆ ਛਾਂਟੀ ਕਰਨ ਵਾਲੇ ਐਲਗੋਰਿਦਮ ਸਭ ਤੋਂ ਵੱਧ ਕੁਸ਼ਲ ਹਨ ਕਿਉਂਕਿ ਉਹਨਾਂ ਦੀ ਗੁੰਝਲਤਾ O(nlogn) ਹੈ। ਤੱਥ ਇਹ ਹੈ ਕਿ ਐਨ ਹਨ! ਚੀਜ਼ਾਂ ਨੂੰ ਸੰਗਠਿਤ ਕਰਨ ਦੇ ਤਰੀਕੇ ਇਸ ਹੇਠਲੇ ਸੀਮਾ ਵੱਲ ਲੈ ਜਾਂਦੇ ਹਨ। ਕਿਉਂਕਿ ਹਰੇਕ ਤੁਲਨਾ n ਦੇ ਇਸ ਸੰਗ੍ਰਹਿ ਨੂੰ ਵੰਡਦੀ ਹੈ! ਆਰਡਰ ਨੂੰ ਦੋ ਟੁਕੜਿਆਂ ਵਿੱਚ ਵੰਡੋ, ਸਾਰੇ ਆਰਡਰਾਂ ਨੂੰ ਵੱਖ ਕਰਨ ਲਈ ਲੋੜੀਂਦੇ N ਤੁਲਨਾਵਾਂ ਦੀ ਸੰਖਿਆ 2N > n! ਹੋਣੀ ਚਾਹੀਦੀ ਹੈ, ਸਟਰਲਿੰਗ ਦੇ ਫਾਰਮੂਲੇ ਦੁਆਰਾ O(nlogn) ਨੂੰ ਦਰਸਾਉਂਦਾ ਹੈ।

ਇੱਕ ਸਮੱਸਿਆ ਨੂੰ ਦੂਸਰੀ ਸਮੱਸਿਆ ਵਿੱਚ ਘਟਾਉਣਾ ਘੱਟ ਗੁੰਝਲਦਾਰ ਰੁਕਾਵਟਾਂ ਨੂੰ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਇੱਕ ਆਮ ਰਣਨੀਤੀ ਹੈ।

ਐਲਗੋਰਿਦਮ ਵਿਕਾਸ

ਇੱਕ ਐਲਗੋਰਿਦਮ ਦੀ ਗੁੰਝਲਤਾ ਦਾ ਮੁਲਾਂਕਣ ਕਰਨਾ ਡਿਜ਼ਾਈਨ ਪ੍ਰਕਿਰਿਆ ਦਾ ਇੱਕ ਮਹੱਤਵਪੂਰਨ ਤੱਤ ਹੈ ਕਿਉਂਕਿ ਇਹ ਉਸ ਪ੍ਰਦਰਸ਼ਨ ਬਾਰੇ ਉਪਯੋਗੀ ਜਾਣਕਾਰੀ ਪ੍ਰਦਾਨ ਕਰਦਾ ਹੈ ਜਿਸਦੀ ਉਮੀਦ ਕੀਤੀ ਜਾ ਸਕਦੀ ਹੈ।

ਇਹ ਇੱਕ ਅਕਸਰ ਗਲਤਫਹਿਮੀ ਹੈ ਕਿ, ਮੂਰ ਦੇ ਕਾਨੂੰਨ ਦੇ ਨਤੀਜੇ ਵਜੋਂ, ਜੋ ਕਿ ਆਧੁਨਿਕ ਕੰਪਿਊਟਰ ਸ਼ਕਤੀ ਦੇ ਘਾਤਕ ਵਾਧੇ ਦੀ ਭਵਿੱਖਬਾਣੀ ਕਰਦਾ ਹੈ, ਐਲਗੋਰਿਦਮ ਦੀ ਗੁੰਝਲਤਾ ਦਾ ਮੁਲਾਂਕਣ ਕਰਨਾ ਘੱਟ ਪ੍ਰਸੰਗਿਕ ਹੋ ਜਾਵੇਗਾ। ਇਹ ਗਲਤ ਹੈ ਕਿਉਂਕਿ ਵਧੀ ਹੋਈ ਪਾਵਰ ਵੱਡੀ ਮਾਤਰਾ ਵਿੱਚ ਡੇਟਾ (ਵੱਡੇ ਡੇਟਾ) ਦੀ ਪ੍ਰੋਸੈਸਿੰਗ ਦੀ ਆਗਿਆ ਦਿੰਦੀ ਹੈ। ਉਦਾਹਰਨ ਲਈ, ਕਿਸੇ ਵੀ ਐਲਗੋਰਿਦਮ ਨੂੰ ਇੱਕ ਸਕਿੰਟ ਤੋਂ ਵੀ ਘੱਟ ਸਮੇਂ ਵਿੱਚ ਚੰਗੀ ਤਰ੍ਹਾਂ ਕੰਮ ਕਰਨਾ ਚਾਹੀਦਾ ਹੈ ਜਦੋਂ ਵਰਣਮਾਲਾ ਅਨੁਸਾਰ ਕੁਝ ਸੈਂਕੜੇ ਐਂਟਰੀਆਂ ਦੀ ਸੂਚੀ ਨੂੰ ਛਾਂਟਣਾ ਚਾਹੀਦਾ ਹੈ, ਜਿਵੇਂ ਕਿ ਕਿਸੇ ਕਿਤਾਬ ਦੀ ਪੁਸਤਕ ਸੂਚੀ। ਦੂਜੇ ਪਾਸੇ, ਇੱਕ ਮਿਲੀਅਨ ਐਂਟਰੀਆਂ ਲਈ (ਉਦਾਹਰਨ ਲਈ, ਇੱਕ ਵੱਡੇ ਸ਼ਹਿਰ ਦੇ ਫ਼ੋਨ ਨੰਬਰ), ਬੁਨਿਆਦੀ ਐਲਗੋਰਿਦਮ ਜਿਨ੍ਹਾਂ ਲਈ O(n2) ਤੁਲਨਾਵਾਂ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ, ਨੂੰ ਇੱਕ ਟ੍ਰਿਲੀਅਨ ਤੁਲਨਾ ਕਰਨੀ ਪਵੇਗੀ, ਜਿਸ ਵਿੱਚ 10 ਦੀ ਗਤੀ ਨਾਲ ਤਿੰਨ ਘੰਟੇ ਲੱਗਣਗੇ। ਪ੍ਰਤੀ ਸਕਿੰਟ ਮਿਲੀਅਨ ਤੁਲਨਾਵਾਂ। ਦੂਜੇ ਪਾਸੇ, Quicksort ਅਤੇ Merge sort ਲਈ, ਸਿਰਫ਼ nlogn ਤੁਲਨਾਵਾਂ ਦੀ ਲੋੜ ਹੁੰਦੀ ਹੈ (ਪੂਰਵ ਲਈ ਔਸਤ-ਕੇਸ ਜਟਿਲਤਾ ਦੇ ਤੌਰ 'ਤੇ, ਬਾਅਦ ਵਾਲੇ ਲਈ ਸਭ ਤੋਂ ਮਾੜੇ-ਕੇਸ ਜਟਿਲਤਾ ਵਜੋਂ)। ਇਹ n = 30,000,000 ਲਈ ਲਗਭਗ 1,000,000 ਤੁਲਨਾਵਾਂ ਪੈਦਾ ਕਰਦਾ ਹੈ, ਜੋ ਪ੍ਰਤੀ ਸਕਿੰਟ 3 ਮਿਲੀਅਨ ਤੁਲਨਾਵਾਂ 'ਤੇ ਸਿਰਫ 10 ਸਕਿੰਟ ਲਵੇਗਾ।

ਨਤੀਜੇ ਵਜੋਂ, ਜਟਿਲਤਾ ਦਾ ਮੁਲਾਂਕਣ ਲਾਗੂ ਕਰਨ ਤੋਂ ਪਹਿਲਾਂ ਬਹੁਤ ਸਾਰੇ ਅਕੁਸ਼ਲ ਐਲਗੋਰਿਦਮ ਨੂੰ ਖਤਮ ਕਰਨ ਦੀ ਇਜਾਜ਼ਤ ਦੇ ਸਕਦਾ ਹੈ। ਇਸਦੀ ਵਰਤੋਂ ਸਾਰੇ ਸੰਭਾਵੀ ਰੂਪਾਂ ਦੀ ਜਾਂਚ ਕੀਤੇ ਬਿਨਾਂ ਗੁੰਝਲਦਾਰ ਐਲਗੋਰਿਦਮ ਨੂੰ ਵਧੀਆ ਬਣਾਉਣ ਲਈ ਵੀ ਕੀਤੀ ਜਾ ਸਕਦੀ ਹੈ। ਜਟਿਲਤਾ ਦਾ ਅਧਿਐਨ ਇੱਕ ਗੁੰਝਲਦਾਰ ਐਲਗੋਰਿਦਮ ਦੇ ਸਭ ਤੋਂ ਮਹਿੰਗੇ ਕਦਮਾਂ ਨੂੰ ਨਿਰਧਾਰਤ ਕਰਕੇ ਇੱਕ ਲਾਗੂਕਰਨ ਦੀ ਕੁਸ਼ਲਤਾ ਨੂੰ ਵਧਾਉਣ ਲਈ ਯਤਨਾਂ ਨੂੰ ਫੋਕਸ ਕਰਨ ਦੀ ਆਗਿਆ ਦਿੰਦਾ ਹੈ।