EITC/IS/CCTF ਕੰਪਿਊਟੇਸ਼ਨਲ ਜਟਿਲਤਾ ਥਿਊਰੀ ਫੰਡਾਮੈਂਟਲਜ਼ ਕੰਪਿਊਟਰ ਵਿਗਿਆਨ ਦੀ ਬੁਨਿਆਦ ਦੇ ਸਿਧਾਂਤਕ ਪਹਿਲੂਆਂ 'ਤੇ ਯੂਰਪੀਅਨ IT ਪ੍ਰਮਾਣੀਕਰਣ ਪ੍ਰੋਗਰਾਮ ਹੈ ਜੋ ਕਿ ਇੰਟਰਨੈਟ ਵਿੱਚ ਵਿਆਪਕ ਤੌਰ 'ਤੇ ਵਰਤੀ ਜਾਂਦੀ ਕਲਾਸੀਕਲ ਅਸਮੈਟ੍ਰਿਕ ਪਬਲਿਕ-ਕੁੰਜੀ ਕ੍ਰਿਪਟੋਗ੍ਰਾਫੀ ਦਾ ਅਧਾਰ ਵੀ ਹੈ।
EITC/IS/CCTF ਕੰਪਿਊਟੇਸ਼ਨਲ ਕੰਪਲੈਕਸਿਟੀ ਥਿਊਰੀ ਫੰਡਾਮੈਂਟਲ ਦਾ ਪਾਠਕ੍ਰਮ ਕੰਪਿਊਟਰ ਵਿਗਿਆਨ ਦੀ ਬੁਨਿਆਦ ਅਤੇ ਕੰਪਿਊਟੇਸ਼ਨਲ ਮਾਡਲਾਂ ਜਿਵੇਂ ਕਿ ਨਿਰਧਾਰਨਵਾਦੀ ਅਤੇ ਗੈਰ-ਨਿਰਧਾਰਤ ਸੀਮਤ ਰਾਜ ਮਸ਼ੀਨਾਂ, ਨਿਯਮਤ ਭਾਸ਼ਾਵਾਂ, ਸੰਦਰਭ ਮੁਕਤ ਵਿਆਕਰਣ ਅਤੇ ਭਾਸ਼ਾ ਸਿਧਾਂਤ, ਆਟੋਮੇਟਾ ਥਿਊਰੀ, ਟਿਊਰਿੰਗ ਵਰਗੇ ਬੁਨਿਆਦੀ ਸੰਕਲਪਾਂ 'ਤੇ ਸਿਧਾਂਤਕ ਗਿਆਨ ਨੂੰ ਕਵਰ ਕਰਦਾ ਹੈ। ਮਸ਼ੀਨਾਂ, ਸਮੱਸਿਆਵਾਂ ਦੀ ਨਿਰਣਾਇਕਤਾ, ਆਵਰਤੀ, ਤਰਕ ਅਤੇ ਐਲਗੋਰਿਦਮਿਕਸ ਦੀ ਗੁੰਝਲਤਾ ਹੇਠ ਲਿਖੇ ਢਾਂਚੇ ਦੇ ਅੰਦਰ ਬੁਨਿਆਦੀ ਸੁਰੱਖਿਆ ਐਪਲੀਕੇਸ਼ਨਾਂ ਲਈ, ਇਸ EITC ਸਰਟੀਫਿਕੇਸ਼ਨ ਲਈ ਇੱਕ ਸੰਦਰਭ ਦੇ ਤੌਰ 'ਤੇ ਵਿਆਪਕ ਵੀਡੀਓ ਡਾਇਡੈਕਟਿਕ ਸਮੱਗਰੀ ਨੂੰ ਸ਼ਾਮਲ ਕਰਦੇ ਹੋਏ।
ਇੱਕ ਐਲਗੋਰਿਦਮ ਦੀ ਗਣਨਾਤਮਕ ਗੁੰਝਲਤਾ ਇਸ ਨੂੰ ਚਲਾਉਣ ਲਈ ਲੋੜੀਂਦੇ ਸਰੋਤਾਂ ਦੀ ਮਾਤਰਾ ਹੈ। ਸਮੇਂ ਅਤੇ ਯਾਦਦਾਸ਼ਤ ਦੇ ਸਰੋਤਾਂ ਨੂੰ ਵਿਸ਼ੇਸ਼ ਧਿਆਨ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ. ਕਿਸੇ ਸਮੱਸਿਆ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਇਸ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਸਭ ਤੋਂ ਵਧੀਆ ਐਲਗੋਰਿਦਮ ਦੀ ਜਟਿਲਤਾ ਵਜੋਂ ਪਰਿਭਾਸ਼ਿਤ ਕੀਤਾ ਗਿਆ ਹੈ। ਐਲਗੋਰਿਦਮ ਦਾ ਵਿਸ਼ਲੇਸ਼ਣ ਸਪੱਸ਼ਟ ਤੌਰ 'ਤੇ ਦਿੱਤੇ ਗਏ ਐਲਗੋਰਿਦਮ ਦੀ ਗੁੰਝਲਤਾ ਦਾ ਅਧਿਐਨ ਹੈ, ਜਦੋਂ ਕਿ ਕੰਪਿਊਟੇਸ਼ਨਲ ਜਟਿਲਤਾ ਸਿਧਾਂਤ ਸਭ ਤੋਂ ਮਸ਼ਹੂਰ ਐਲਗੋਰਿਦਮ ਨਾਲ ਸਮੱਸਿਆਵਾਂ ਦੇ ਹੱਲ ਦੀ ਗੁੰਝਲਤਾ ਦਾ ਅਧਿਐਨ ਹੈ। ਦੋਵੇਂ ਡੋਮੇਨ ਆਪਸ ਵਿੱਚ ਜੁੜੇ ਹੋਏ ਹਨ ਕਿਉਂਕਿ ਇੱਕ ਐਲਗੋਰਿਦਮ ਦੀ ਗੁੰਝਲਤਾ ਹਮੇਸ਼ਾਂ ਉਸ ਸਮੱਸਿਆ ਦੀ ਗੁੰਝਲਤਾ 'ਤੇ ਇੱਕ ਉਪਰਲੀ ਰੁਕਾਵਟ ਹੁੰਦੀ ਹੈ ਜਿਸ ਨੂੰ ਇਹ ਹੱਲ ਕਰਦਾ ਹੈ। ਇਸ ਤੋਂ ਇਲਾਵਾ, ਕੁਸ਼ਲ ਐਲਗੋਰਿਦਮ ਬਣਾਉਂਦੇ ਸਮੇਂ ਕਿਸੇ ਖਾਸ ਐਲਗੋਰਿਦਮ ਦੀ ਗੁੰਝਲਤਾ ਨੂੰ ਹੱਲ ਕਰਨ ਲਈ ਸਮੱਸਿਆ ਦੀ ਜਟਿਲਤਾ ਨਾਲ ਤੁਲਨਾ ਕਰਨਾ ਅਕਸਰ ਜ਼ਰੂਰੀ ਹੁੰਦਾ ਹੈ। ਜ਼ਿਆਦਾਤਰ ਸਥਿਤੀਆਂ ਵਿੱਚ, ਕਿਸੇ ਸਮੱਸਿਆ ਦੀ ਮੁਸ਼ਕਲ ਦੇ ਸੰਬੰਧ ਵਿੱਚ ਉਪਲਬਧ ਸਿਰਫ ਜਾਣਕਾਰੀ ਇਹ ਹੈ ਕਿ ਇਹ ਸਭ ਤੋਂ ਕੁਸ਼ਲ ਜਾਣੀਆਂ ਗਈਆਂ ਤਕਨੀਕਾਂ ਦੀ ਗੁੰਝਲਤਾ ਤੋਂ ਘੱਟ ਹੈ। ਨਤੀਜੇ ਵਜੋਂ, ਐਲਗੋਰਿਦਮ ਵਿਸ਼ਲੇਸ਼ਣ ਅਤੇ ਜਟਿਲਤਾ ਸਿਧਾਂਤ ਵਿਚਕਾਰ ਬਹੁਤ ਜ਼ਿਆਦਾ ਓਵਰਲੈਪ ਹੁੰਦਾ ਹੈ।
ਜਟਿਲਤਾ ਸਿਧਾਂਤ ਨਾ ਸਿਰਫ਼ ਕੰਪਿਊਟਰ ਵਿਗਿਆਨ ਦੇ ਆਧਾਰ ਵਜੋਂ ਕੰਪਿਊਟੇਸ਼ਨਲ ਮਾਡਲਾਂ ਦੀ ਬੁਨਿਆਦ ਵਿੱਚ ਮਹੱਤਵਪੂਰਨ ਭੂਮਿਕਾ ਨਿਭਾਉਂਦਾ ਹੈ, ਸਗੋਂ ਕਲਾਸੀਕਲ ਅਸਮੈਟ੍ਰਿਕ ਕ੍ਰਿਪਟੋਗ੍ਰਾਫ਼ੀ (ਅਖੌਤੀ ਪਬਲਿਕ-ਕੀ ਕ੍ਰਿਪਟੋਗ੍ਰਾਫੀ) ਦੀ ਬੁਨਿਆਦ ਵਿੱਚ ਵੀ ਮਹੱਤਵਪੂਰਨ ਭੂਮਿਕਾ ਨਿਭਾਉਂਦਾ ਹੈ, ਜੋ ਆਧੁਨਿਕ ਨੈੱਟਵਰਕਾਂ, ਖਾਸ ਕਰਕੇ ਇੰਟਰਨੈੱਟ ਵਿੱਚ ਵਿਆਪਕ ਤੌਰ 'ਤੇ ਪ੍ਰਸਾਰਿਤ ਹੁੰਦਾ ਹੈ। ਪਬਲਿਕ-ਕੁੰਜੀ ਐਨਕ੍ਰਿਪਸ਼ਨ ਕੁਝ ਅਸਮਿਤ ਗਣਿਤਿਕ ਸਮੱਸਿਆਵਾਂ ਦੀ ਗਣਨਾਤਮਕ ਮੁਸ਼ਕਲ 'ਤੇ ਅਧਾਰਤ ਹੈ ਜਿਵੇਂ ਕਿ ਉਦਾਹਰਨ ਲਈ ਵੱਡੀ ਸੰਖਿਆਵਾਂ ਨੂੰ ਇਸਦੇ ਪ੍ਰਮੁੱਖ ਕਾਰਕਾਂ ਵਿੱਚ ਫੈਕਟਰਾਈਜ਼ੇਸ਼ਨ (ਇਹ ਕਾਰਵਾਈ ਜਟਿਲਤਾ ਸਿਧਾਂਤ ਵਰਗੀਕਰਣ ਵਿੱਚ ਇੱਕ ਮੁਸ਼ਕਲ ਸਮੱਸਿਆ ਹੈ, ਕਿਉਂਕਿ ਹੱਲ ਕਰਨ ਲਈ ਕੁਸ਼ਲ ਕਲਾਸੀਕਲ ਐਲਗੋਰਿਦਮ ਨਹੀਂ ਹਨ। ਇਹ ਸਮੱਸਿਆ ਦੇ ਇਨਪੁਟ ਆਕਾਰ ਦੇ ਵਾਧੇ ਦੇ ਨਾਲ ਤੇਜ਼ੀ ਨਾਲ ਵਧਣ ਦੀ ਬਜਾਏ ਬਹੁਪਦ ਦੇ ਰੂਪ ਵਿੱਚ ਸੰਸਾਧਨਾਂ ਨਾਲ ਸਕੇਲਿੰਗ ਕਰਦਾ ਹੈ, ਜੋ ਕਿ ਅਸਲੀ ਵੱਡੀ ਸੰਖਿਆ ਦੇਣ ਲਈ ਜਾਣੇ-ਪਛਾਣੇ ਪ੍ਰਮੁੱਖ ਕਾਰਕਾਂ ਨੂੰ ਗੁਣਾ ਕਰਨ ਦੇ ਇੱਕ ਬਹੁਤ ਹੀ ਸਧਾਰਨ ਰਿਵਰਸ ਓਪਰੇਸ਼ਨ ਦੇ ਉਲਟ ਹੈ)। ਪਬਲਿਕ-ਕੁੰਜੀ ਕ੍ਰਿਪਟੋਗ੍ਰਾਫੀ ਦੇ ਇੱਕ ਢਾਂਚੇ ਵਿੱਚ ਇਸ ਅਸਮਿਤੀ ਦੀ ਵਰਤੋਂ ਕਰਦੇ ਹੋਏ (ਜਨਤਕ ਕੁੰਜੀ ਦੇ ਵਿਚਕਾਰ ਇੱਕ ਗਣਨਾਤਮਕ ਤੌਰ 'ਤੇ ਅਸਮਿਤ ਸਬੰਧ ਨੂੰ ਪਰਿਭਾਸ਼ਿਤ ਕਰਕੇ, ਜੋ ਕਿ ਇੱਕ ਪ੍ਰਾਈਵੇਟ ਕੁੰਜੀ ਤੋਂ ਆਸਾਨੀ ਨਾਲ ਗਣਨਾ ਕੀਤੀ ਜਾ ਸਕਦੀ ਹੈ, ਜਦੋਂ ਕਿ ਪ੍ਰਾਈਵੇਟ ਕੁੰਜੀ ਨੂੰ ਇੱਕ ਜਨਤਕ ਕੁੰਜੀ ਤੋਂ ਆਸਾਨੀ ਨਾਲ ਕੰਪਿਊਟਰ ਨਹੀਂ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ, ਕੋਈ ਜਨਤਕ ਤੌਰ' ਤੇ ਕਰ ਸਕਦਾ ਹੈ। ਜਨਤਕ ਕੁੰਜੀ ਦੀ ਘੋਸ਼ਣਾ ਕਰੋ ਅਤੇ ਹੋਰ ਸੰਚਾਰ ਪੱਖਾਂ ਨੂੰ ਡੇਟਾ ਦੇ ਅਸਮਿਤ ਐਨਕ੍ਰਿਪਸ਼ਨ ਲਈ ਇਸਦੀ ਵਰਤੋਂ ਕਰਨ ਦੇ ਯੋਗ ਬਣਾਓ, ਜਿਸ ਨੂੰ ਸਿਰਫ ਜੋੜੀ ਗਈ ਪ੍ਰਾਈਵੇਟ ਕੁੰਜੀ ਨਾਲ ਡੀਕ੍ਰਿਪਟ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ, ਜੋ ਕਿ ਤੀਜੀ ਧਿਰ ਲਈ ਗਣਨਾਤਮਕ ਤੌਰ 'ਤੇ ਉਪਲਬਧ ਨਹੀਂ ਹੈ, ਇਸ ਤਰ੍ਹਾਂ ਸੰਚਾਰ ਨੂੰ ਸੁਰੱਖਿਅਤ ਬਣਾਉਂਦਾ ਹੈ)।
ਕੰਪਿਊਟੇਸ਼ਨਲ ਜਟਿਲਤਾ ਸਿਧਾਂਤ ਮੁੱਖ ਤੌਰ 'ਤੇ ਕੰਪਿਊਟਰ ਵਿਗਿਆਨ ਅਤੇ ਐਲਗੋਰਿਦਮਿਕਸ ਪਾਇਨੀਅਰਾਂ ਦੀਆਂ ਪ੍ਰਾਪਤੀਆਂ 'ਤੇ ਵਿਕਸਤ ਕੀਤਾ ਗਿਆ ਸੀ, ਜਿਵੇਂ ਕਿ ਐਲਨ ਟਿਊਰਿੰਗ, ਜਿਸਦਾ ਕੰਮ ਨਾਜ਼ੀ ਜਰਮਨੀ ਦੇ ਏਨਿਗਮਾ ਸਿਫਰ ਨੂੰ ਤੋੜਨ ਲਈ ਮਹੱਤਵਪੂਰਨ ਸੀ, ਜਿਸ ਨੇ ਦੂਜੇ ਵਿਸ਼ਵ ਯੁੱਧ ਨੂੰ ਜਿੱਤਣ ਵਾਲੇ ਸਹਿਯੋਗੀਆਂ ਵਿੱਚ ਡੂੰਘੀ ਭੂਮਿਕਾ ਨਿਭਾਈ ਸੀ। ਗੁਪਤ ਜਾਣਕਾਰੀ ਦਾ ਪਰਦਾਫਾਸ਼ ਕਰਨ ਲਈ ਡੇਟਾ (ਮੁੱਖ ਤੌਰ 'ਤੇ ਏਨਕ੍ਰਿਪਟਡ ਸੰਚਾਰ) ਦੇ ਵਿਸ਼ਲੇਸ਼ਣ ਦੀਆਂ ਗਣਨਾਤਮਕ ਪ੍ਰਕਿਰਿਆਵਾਂ ਨੂੰ ਤਿਆਰ ਕਰਨ ਅਤੇ ਸਵੈਚਲਿਤ ਕਰਨ ਦਾ ਉਦੇਸ਼ ਕ੍ਰਿਪਟੋਗ੍ਰਾਫਿਕ ਪ੍ਰਣਾਲੀਆਂ ਦੀ ਉਲੰਘਣਾ ਕਰਨ ਅਤੇ ਏਨਕ੍ਰਿਪਟਡ ਸੰਚਾਰ ਦੀਆਂ ਸਮੱਗਰੀਆਂ ਤੱਕ ਪਹੁੰਚ ਪ੍ਰਾਪਤ ਕਰਨ ਲਈ ਵਰਤਿਆ ਜਾਂਦਾ ਸੀ, ਆਮ ਤੌਰ 'ਤੇ ਰਣਨੀਤਕ ਫੌਜੀ ਮਹੱਤਵ ਵਾਲਾ। ਇਹ ਕ੍ਰਿਪਟ ਵਿਸ਼ਲੇਸ਼ਣ ਵੀ ਸੀ ਜਿਸ ਨੇ ਪਹਿਲੇ ਆਧੁਨਿਕ ਕੰਪਿਊਟਰਾਂ ਦੇ ਵਿਕਾਸ ਨੂੰ ਉਤਪ੍ਰੇਰਿਤ ਕੀਤਾ (ਜੋ ਸ਼ੁਰੂ ਵਿੱਚ ਕੋਡਬ੍ਰੇਕਿੰਗ ਦੇ ਰਣਨੀਤਕ ਟੀਚੇ ਲਈ ਲਾਗੂ ਕੀਤੇ ਗਏ ਸਨ)। ਬ੍ਰਿਟਿਸ਼ ਕੋਲੋਸਸ (ਪਹਿਲੇ ਆਧੁਨਿਕ ਇਲੈਕਟ੍ਰਾਨਿਕ ਅਤੇ ਪ੍ਰੋਗਰਾਮ ਕੰਪਿਊਟਰ ਵਜੋਂ ਮੰਨਿਆ ਜਾਂਦਾ ਹੈ) ਪੋਲਿਸ਼ "ਬੰਬ" ਤੋਂ ਪਹਿਲਾਂ ਬਣਾਇਆ ਗਿਆ ਸੀ, ਇੱਕ ਇਲੈਕਟ੍ਰਾਨਿਕ ਕੰਪਿਊਟੇਸ਼ਨਲ ਯੰਤਰ ਜਿਸਨੂੰ ਮਾਰੀਅਨ ਰੇਜੇਵਸਕੀ ਦੁਆਰਾ ਏਨਿਗਮਾ ਸਿਫਰਾਂ ਨੂੰ ਤੋੜਨ ਵਿੱਚ ਸਹਾਇਤਾ ਕਰਨ ਲਈ ਡਿਜ਼ਾਇਨ ਕੀਤਾ ਗਿਆ ਸੀ, ਅਤੇ ਪੋਲਿਸ਼ ਖੁਫੀਆ ਏਜੰਸੀ ਦੁਆਰਾ ਗ੍ਰੇਟ ਬ੍ਰਿਟੇਨ ਨੂੰ ਸੌਂਪਿਆ ਗਿਆ ਸੀ। 1939 ਵਿੱਚ ਜਰਮਨੀ ਦੁਆਰਾ ਪੋਲੈਂਡ ਉੱਤੇ ਹਮਲਾ ਕੀਤੇ ਜਾਣ ਤੋਂ ਬਾਅਦ, ਕੈਪਚਰ ਕੀਤੀ ਜਰਮਨ ਏਨਿਗਮਾ ਐਨਕ੍ਰਿਪਸ਼ਨ ਮਸ਼ੀਨ। ਇਸ ਡਿਵਾਈਸ ਦੇ ਅਧਾਰ ਤੇ ਐਲਨ ਟਿਊਰਿੰਗ ਨੇ ਜਰਮਨ ਐਨਕ੍ਰਿਪਟਡ ਸੰਚਾਰ ਨੂੰ ਸਫਲਤਾਪੂਰਵਕ ਤੋੜਨ ਲਈ ਆਪਣੇ ਵਧੇਰੇ ਉੱਨਤ ਹਮਰੁਤਬਾ ਵਿਕਸਿਤ ਕੀਤਾ, ਜਿਸਨੂੰ ਬਾਅਦ ਵਿੱਚ ਆਧੁਨਿਕ ਕੰਪਿਊਟਰਾਂ ਵਿੱਚ ਵਿਕਸਤ ਕੀਤਾ ਗਿਆ ਹੈ।
ਕਿਉਂਕਿ ਇੱਕ ਐਲਗੋਰਿਦਮ ਨੂੰ ਚਲਾਉਣ ਲਈ ਲੋੜੀਂਦੇ ਸਰੋਤਾਂ ਦੀ ਮਾਤਰਾ ਇਨਪੁਟ ਦੇ ਆਕਾਰ ਦੇ ਨਾਲ ਬਦਲਦੀ ਹੈ, ਇਸ ਲਈ ਜਟਿਲਤਾ ਨੂੰ ਆਮ ਤੌਰ 'ਤੇ ਇੱਕ ਫੰਕਸ਼ਨ 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 ਸਕਿੰਟ ਲਵੇਗਾ।
ਨਤੀਜੇ ਵਜੋਂ, ਜਟਿਲਤਾ ਦਾ ਮੁਲਾਂਕਣ ਲਾਗੂ ਕਰਨ ਤੋਂ ਪਹਿਲਾਂ ਬਹੁਤ ਸਾਰੇ ਅਕੁਸ਼ਲ ਐਲਗੋਰਿਦਮ ਨੂੰ ਖਤਮ ਕਰਨ ਦੀ ਇਜਾਜ਼ਤ ਦੇ ਸਕਦਾ ਹੈ। ਇਸਦੀ ਵਰਤੋਂ ਸਾਰੇ ਸੰਭਾਵੀ ਰੂਪਾਂ ਦੀ ਜਾਂਚ ਕੀਤੇ ਬਿਨਾਂ ਗੁੰਝਲਦਾਰ ਐਲਗੋਰਿਦਮ ਨੂੰ ਵਧੀਆ ਬਣਾਉਣ ਲਈ ਵੀ ਕੀਤੀ ਜਾ ਸਕਦੀ ਹੈ। ਜਟਿਲਤਾ ਦਾ ਅਧਿਐਨ ਇੱਕ ਗੁੰਝਲਦਾਰ ਐਲਗੋਰਿਦਮ ਦੇ ਸਭ ਤੋਂ ਮਹਿੰਗੇ ਕਦਮਾਂ ਨੂੰ ਨਿਰਧਾਰਤ ਕਰਕੇ ਇੱਕ ਲਾਗੂਕਰਨ ਦੀ ਕੁਸ਼ਲਤਾ ਨੂੰ ਵਧਾਉਣ ਲਈ ਯਤਨਾਂ ਨੂੰ ਫੋਕਸ ਕਰਨ ਦੀ ਆਗਿਆ ਦਿੰਦਾ ਹੈ।
ਪ੍ਰਮਾਣੀਕਰਣ ਪਾਠਕ੍ਰਮ ਨਾਲ ਆਪਣੇ ਆਪ ਨੂੰ ਵਿਸਥਾਰ ਵਿੱਚ ਜਾਣੂ ਕਰਵਾਉਣ ਲਈ ਤੁਸੀਂ ਹੇਠਾਂ ਦਿੱਤੀ ਸਾਰਣੀ ਦਾ ਵਿਸਤਾਰ ਅਤੇ ਵਿਸ਼ਲੇਸ਼ਣ ਕਰ ਸਕਦੇ ਹੋ।
EITC/IS/CCTF ਕੰਪਿਊਟੇਸ਼ਨਲ ਜਟਿਲਤਾ ਥਿਊਰੀ ਫੰਡਾਮੈਂਟਲ ਸਰਟੀਫਿਕੇਸ਼ਨ ਪਾਠਕ੍ਰਮ ਇੱਕ ਵੀਡੀਓ ਰੂਪ ਵਿੱਚ ਓਪਨ-ਐਕਸੈਸ ਡਾਇਡੈਕਟਿਕ ਸਮੱਗਰੀ ਦਾ ਹਵਾਲਾ ਦਿੰਦਾ ਹੈ। ਸਿੱਖਣ ਦੀ ਪ੍ਰਕਿਰਿਆ ਨੂੰ ਇੱਕ ਕਦਮ-ਦਰ-ਕਦਮ ਢਾਂਚੇ (ਪ੍ਰੋਗਰਾਮ -> ਪਾਠ -> ਵਿਸ਼ੇ) ਵਿੱਚ ਵੰਡਿਆ ਗਿਆ ਹੈ ਜੋ ਪਾਠਕ੍ਰਮ ਦੇ ਸੰਬੰਧਿਤ ਹਿੱਸਿਆਂ ਨੂੰ ਕਵਰ ਕਰਦਾ ਹੈ। ਡੋਮੇਨ ਮਾਹਰਾਂ ਨਾਲ ਅਸੀਮਤ ਸਲਾਹ ਵੀ ਪ੍ਰਦਾਨ ਕੀਤੀ ਜਾਂਦੀ ਹੈ।
ਸਰਟੀਫਿਕੇਸ਼ਨ ਪ੍ਰਕਿਰਿਆ ਦੇ ਵੇਰਵਿਆਂ ਲਈ ਜਾਂਚ ਕਰੋ ਕਿਦਾ ਚਲਦਾ.
ਪ੍ਰਾਇਮਰੀ ਸਹਾਇਕ ਪਾਠਕ੍ਰਮ ਪੜ੍ਹਨ ਸਮੱਗਰੀ
ਐਸ. ਅਰੋੜਾ, ਬੀ. ਬਾਰਕ, ਕੰਪਿਊਟੇਸ਼ਨਲ ਕੰਪਲੈਕਸੀਟੀ: ਏ ਮਾਡਰਨ ਅਪਰੋਚ
https://theory.cs.princeton.edu/complexity/book.pdf
ਸੈਕੰਡਰੀ ਸਹਾਇਕ ਪਾਠਕ੍ਰਮ ਪੜ੍ਹਨ ਸਮੱਗਰੀ
ਓ. ਗੋਲਡਰੀਚ, ਜਟਿਲਤਾ ਸਿਧਾਂਤ ਦੀ ਜਾਣ-ਪਛਾਣ:
https://www.wisdom.weizmann.ac.il/~oded/cc99.html
ਵੱਖਰੇ ਗਣਿਤ 'ਤੇ ਸਹਾਇਕ ਪਾਠਕ੍ਰਮ ਪੜ੍ਹਨ ਸਮੱਗਰੀ
ਜੇ. ਐਸਪਨੇਸ, ਡਿਸਕ੍ਰਿਟ ਮੈਥੇਮੈਟਿਕਸ 'ਤੇ ਨੋਟਸ:
https://www.cs.yale.edu/homes/aspnes/classes/202/notes.pdf
ਗ੍ਰਾਫ ਥਿਊਰੀ 'ਤੇ ਸਹਾਇਕ ਪਾਠਕ੍ਰਮ ਪੜ੍ਹਨ ਸਮੱਗਰੀ
ਆਰ. ਡੀਸਟਲ, ਗ੍ਰਾਫ ਥਿਊਰੀ:
https://diestel-graph-theory.com/
EITC/IS/CCTF ਕੰਪਿਊਟੇਸ਼ਨਲ ਕੰਪਲੈਕਸਿਟੀ ਥਿਊਰੀ ਫੰਡਾਮੈਂਟਲ ਪ੍ਰੋਗਰਾਮ ਲਈ ਪੂਰੀ ਔਫਲਾਈਨ ਸਵੈ-ਸਿੱਖਣ ਦੀ ਤਿਆਰੀ ਸਮੱਗਰੀ ਨੂੰ ਇੱਕ PDF ਫਾਈਲ ਵਿੱਚ ਡਾਊਨਲੋਡ ਕਰੋ
EITC/IS/CCTF ਤਿਆਰੀ ਸਮੱਗਰੀ - ਮਿਆਰੀ ਸੰਸਕਰਣ
EITC/IS/CCTF ਤਿਆਰੀ ਸਮੱਗਰੀ - ਸਮੀਖਿਆ ਪ੍ਰਸ਼ਨਾਂ ਦੇ ਨਾਲ ਵਿਸਤ੍ਰਿਤ ਸੰਸਕਰਣ